【二分图】【最大匹配】【匈牙利算法】CODEVS 2776 寻找代表元

浏览数：25 / 时间：2015年06月08日

裸的匈牙利，存模板。

 1 #include<cstdio>
 2 #include<vector>
 3 #include<cstring>
 4 using namespace std;
 5 #define N 201
 6 int n,m,x;
 7 vector<int>G[N<<1];
 8 typedef vector<int>::iterator ITER;
 9 int mat[N<<1]; bool vis[N<<1];
10 bool dfs(int U)
11 {
12     for(ITER it=G[U].begin();it!=G[U].end();it++)
13       if(!vis[*it])
14         {
15           vis[*it]=1;
16           if(mat[*it]==-1||dfs(mat[*it]))
17             {
18               mat[*it]=U;
19               return 1;
20             }
21         }
22       return 0;
23 }
24 int max_match()
25 {
26     int res=0; memset(mat,-1,sizeof(mat));
27     for(int i=1;i<=n;i++)
28       {
29         memset(vis,0,sizeof(vis));
30         if(dfs(i)) res++;
31       }
32     return res;
33 }
34 int main()
35 {
36     scanf("%d%d",&n,&m);
37     for(int i=1;i<=n;i++)
38       {
39         while(1)
40           {
41             scanf("%d",&x);
42             if(!x) break;
43             G[i].push_back(x+n);
44             G[x+n].push_back(i);
45           }
46       }
47     printf("%d\n",max_match());
48     for(;;);
49     return 0;
50 }

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： 编程语言 Java C C# Javascript js Python Ruby Spring 程序 VB

相关文章

随机文章

您可能还喜欢

您可能还喜欢