Ural1109_Conference(二分图最大匹配/匈牙利算法/网络最大流)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Ural1109_Conference(二分图最大匹配/匈牙利算法/网络最大流),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3427字,纯文字阅读大概需要5分钟。
内容图文
解题报告
二分图第一题。
题目描述:
为了参加即将召开的会议,A国派出M位代表,B国派出N位代表,(N,M<=1000)
会议召开前,选出K队代表,每对代表必须一个是A国的,一个是B国的;
要求每一个代表要与另一方的一个代表联系,除了可以直接联系,也可以电话联系,求电话联系最少
思路:
电话联系最少就要使直接联系最大,又是一一匹配关系,就是二分图的最大匹配。
下面是匈牙利算法。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 1050 #define M 1050 using namespace std; int mmap[M][N],vis[N],pre[N],n,m,k; int dfs(int x) { for(int i=1;i<=n;i++) { if(!vis[i]&&mmap[x][i]) { vis[i]=1; if(pre[i]==-1||dfs(pre[i])) { pre[i]=x; return 1; } } } return 0; } int main() { int i,j,u,v; memset(pre,-1,sizeof(pre)); memset(vis,0,sizeof(vis)); scanf("%d%d%d",&m,&n,&k); for(i=0;i<k;i++) { scanf("%d%d",&u,&v); mmap[u][v]=1; } int ans=0; for(i=1;i<=m;i++) { memset(vis,0,sizeof(vis)); ans+=dfs(i); } printf("%d\n",n+m-ans); }
二分最大匹配也可以用最大流做,当试试模板
#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define inf 99999999 #define N 1050 #define M 1050 using namespace std; int mmap[M+N][N+M],vis[N],l[N+M],n,m,k; int bfs() { queue<int>Q; Q.push(0); memset(l,-1,sizeof(l)); l[0]=0; while(!Q.empty()) { int u=Q.front(); Q.pop(); for(int i=0;i<=n+m+1;i++) { if(l[i]==-1&&mmap[u][i]) { l[i]=l[u]+1; Q.push(i); } } } if(l[n+m+1]>0) return 1; return 0; } int dfs(int x,int f) { int a,i; if(x==n+m+1) return f; for(i=0;i<=n+m+1;i++) { if(mmap[x][i]&&l[i]==l[x]+1&&(a=dfs(i,min(f,mmap[x][i])))) { mmap[x][i]-=a; mmap[i][x]+=a; return a; } } return 0; } int main() { int i,j,u,v; memset(vis,0,sizeof(vis)); scanf("%d%d%d",&m,&n,&k); for(i=1;i<=m;i++) mmap[0][i]=1; for(i=m+1;i<=m+n;i++) mmap[i][m+n+1]=1; for(i=0;i<k;i++) { scanf("%d%d",&u,&v); mmap[u][v+m]=1; } int ans=0,a; while(bfs()) while(a=dfs(0,inf)) ans+=a; printf("%d\n",n+m-ans); }
Conference
Memory limit: 64 MB
Input
Output
Sample
input | output |
---|---|
3 2 4 1 1 2 1 3 1 3 2 |
3 |
原文:http://blog.csdn.net/juncoder/article/details/38088263
内容总结
以上是互联网集市为您收集整理的Ural1109_Conference(二分图最大匹配/匈牙利算法/网络最大流)全部内容,希望文章能够帮你解决Ural1109_Conference(二分图最大匹配/匈牙利算法/网络最大流)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。