UPC-5063-二分图最大匹配
好吧二分图的最小点覆盖=最大匹配
这道题也就变成模板题了。。。
写一个提醒，在写二分图时，尽量清零操作清空为-1，比如这个题，匹配数组girl[]如果清空为0，代表每个点都与0点连接，但是实际上是并没有
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; bool line[300][300]; bool used[300]; int girl[300]; int m,n,e; bool findd(int x){ for (int i=0;i<=n-1;i++){//右边匹配情况 if (line[x][i]==1 && used[i]==false) { used[i]=1; if (girl[i]==-1 || findd(girl[i])) { girl[i]=x; return 1; } } } return 0; } int main(){ int a; while(~scanf("%d",&m)){ if (m==0)break; memset(line,0,sizeof(line)); memset(used,0,sizeof(used)); memset(girl,-1,sizeof(girl)); scanf("%d%d",&n,&e); int sum=0; int x,y; while(e--){ scanf("%d%d",&x,&y); line[x][y]=1; } for (int i=0;i<=m-1;i++){ memset(used,0,sizeof(used)); if (findd(i))sum++; } printf("%d\n",sum); } return 0; }
