首页 > 代码库 > 【二分图】【最大匹配】【匈牙利算法】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 寻找代表元
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。