毒瘤出题人zzk出了个二分图匹配的题(18.10.04模拟赛T2),逼我来学二分图匹配。
网络流什么的llx讲完之后有点懵,还是匈牙利比较好理解(绿与被绿)。
对于左边的点一个一个匹配,记录右边哪个点跟左边的i匹配:cp[i]
如果还没有配对,就直接配上。
如果已经有匹配了,每次dfs找增广路(看看能不能换一下),如果成功,那么匹配数增加一。
1 #include2 #include 3 #include 4 using namespace std; 5 6 int n,m,ec,ans; 7 int e[1005][1005]; 8 int cp[1005]; 9 int used[1005];10 11 int dfs(int p)12 {13 for(int i=1;i<=m;i++)14 {15 if(!used[i]&&e[p][i])16 {17 used[i]=1;18 if(!cp[i]||dfs(cp[i]))19 {20 cp[i]=p;21 return 1;22 }23 }24 }25 return 0;26 }27 28 void hungary()29 {30 ans=0;31 for(int i=1;i<=n;i++)32 {33 memset(used,0,sizeof(used));34 if(dfs(i))ans++;35 }36 }37 38 int main()39 {40 scanf("%d%d%d",&n,&m,&ec);41 for(int i=1;i<=ec;i++)42 {43 int a,b;44 scanf("%d%d",&a,&b);45 e[a][b]=1;46 }47 hungary();48 printf("%d",ans);49 return 0;50 }