hdu 1150 Machine Schedule (经典二分匹配)

//A组n人 B组m人 //最多有多少人匹配 每人仅仅有匹配一次 # include<stdio.h> # include<string.h> # include<algorithm> using namespace std; int n,m,k; int pp[1100][1100],map[1100],vis[1100]; int bfs(int x)//二分匹配模板 {for(int i=1;i<=m;i++)//B组中的人来迎合匹配{if(!vis[i]&&pp[x][i]){vis[i]=1;if(!map[i]||bfs(map[i]))//b中i还没匹配或与之匹配的A组中的数（map[i]）还能找到其它人匹配{map[i]=x;return 1;}}}return 0; } int main() {int count,i,a,b,c;while(~scanf("%d",&n),n){memset(pp,0,sizeof(pp));//是否匹配memset(map,0,sizeof(map));scanf("%d%d",&m,&k);for(i=0;i<k;i++){scanf("%d%d%d",&a,&b,&c);pp[b][c]=1;}count=0;//匹配数for(i=1;i<=n;i++)//A组中的人进行匹配{memset(vis,0,sizeof(vis));if(bfs(i))count++;}printf("%d\n",count);}return 0; }

转载于:https://www.cnblogs.com/mengfanrong/p/4094198.html

总结

以上是生活随笔为你收集整理的hdu 1150 Machine Schedule (经典二分匹配)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。