HDU 2458 Kindergarten【二分图之反建边】
原题连接:http://acm.hdu.edu.cn/showproblem.php?pid=2458
题意:…………
思路:反键边求最小点集覆盖key,boys+girls-key 就是答案。根据题意:反建边后,每条边代表的是该男孩和该女孩不认识,求的最小点集,把这些点去掉后即所有反建的边被去掉,则剩余的就是男女之间都相互认识。。
AC代码:
#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int Max = 300;bool use[Max];int link[Max];bool map[Max][Max];void init(){ memset(map,true,sizeof(map));}bool Dfs(int k,int m){ int i,j; for(i=1;i<=m;i++) { if(map[k][i]&&use[i]) { use[i] = false; if(!link[i]||Dfs(link[i],m)) { link[i] = k; return true; } } } return false;}int MaxMatch(int n,int m){ int i,j; int ans = 0; memset(link,0,sizeof(link)); for(i=1;i<=n;i++) { memset(use,true,sizeof(use)); if(Dfs(i,m)) ans++; } return ans;}int main(){ int i,j,n,m,k; int ncase = 1; while(scanf("%d%d%d",&n,&m,&k)&&(n+k+m)) { init(); while(k--) { scanf("%d%d",&i,&j); map[i][j] = false; } printf("Case %d: ",ncase++); printf("%d\n",n+m-MaxMatch(n,m)); } return 0;}