首页 > 代码库 > timus 1109 Conference(二分图匹配)
timus 1109 Conference(二分图匹配)
Conference
Time limit: 0.5 second
Memory limit: 64 MB
Memory limit: 64 MB
On the upcoming conference were sent M representatives of country A and N representatives of country B (M and N ≤ 1000). The representatives were identified with 1, 2, …, M for country A and 1, 2, …, N for country B. Before the conference K pairs of representatives were chosen. Every such pair consists of one member of delegation A and one of delegation B. If there exists a pair in which both member #i of A and member #j of B are included then #i and #j can negotiate. Everyone attending the conference was included in at least one pair. The CEO of the congress center wants to build direct telephone connections between the rooms of the delegates, so that everyone is connected with at least one representative of the other side, and every connection is made between people that can negotiate. The CEO also wants to minimize the amount of telephone connections. Write a program which given M, N, K and K pairs of representatives, finds the minimum number of needed connections.
Input
The first line of the input contains M, N and K. The following K lines contain the choosen pairs in the form of two integers p1 and p2, p1 is member of A and p2 is member of B.
Output
The output should contain the minimum number of needed telephone connections.
Sample
| input | output |
|---|---|
3 2 41 12 13 13 2 | 3 |
Problem Source: Bulgarian National Olympiad Day #1
【分析】最小路径覆盖数 == 总顶点数 - 二分匹配数。
#include <iostream>#include <cstring>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <time.h>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#define inf 0x3f3f3f3f#define mod 10000typedef long long ll;using namespace std;const int N=1005;const int M=100005;int n,m,k,x,y,pre[N];//二分图中X集和Y集的节点数各为n、m，边数为k；匹配边集为pre，其中节点i所在的匹配边为(pre[i],i)bool v[N],a[N][N];//设二分图相邻矩阵为a，Y集合中节点的访问标志为v，若Y集合中的节点j已访问，则v[j]=truebool dfs(int i) { //判断以X集合中的节点i为起点的增广路径是否存在 int j; for(j=1; j<=m; j++) { if(!v[j]&&a[i][j]) { //搜索所有与i相邻的未访问点 v[j]=1;//访问节点j if(pre[j]==-1||dfs(pre[j])) { //若j的前驱是未盖点或者存在由j的前驱出发的增广路径，则设定(i,j)为匹配边，返回成功标志 pre[j]=i; return true; } } } return false;//返回失败标志}int main() { int i,ans; scanf("%d%d%d",&n,&m,&k); memset(a,0,sizeof(a));//二分图的相邻矩阵初始化 memset(pre,-1,sizeof(pre));//匹配边集初始化为空 for(i=1; i<=k; i++) { scanf("%d%d",&x,&y); a[x][y]=1; } ans=0;//匹配边数初始化为0 for(i=1; i<=n; i++) { //枚举X集的每个节点 memset(v,0,sizeof(v));//设Y集合中的所有节点的未访问标志 if(dfs(i)) ans++;//若节点i被匹配边覆盖，则匹配边数+1 } printf("%d\n",n+m-ans); return 0;}
timus 1109 Conference(二分图匹配)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。