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

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

裸的匈牙利,存模板。

 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 }

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