首页 / 算法 / HDU2255-奔小康赚大钱-二分图最大权值匹配-KM算法

HDU2255-奔小康赚大钱-二分图最大权值匹配-KM算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了HDU2255-奔小康赚大钱-二分图最大权值匹配-KM算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2451字，纯文字阅读大概需要4分钟。

内容图文

二分图最大权值匹配问题。用KM算法。

最小权值的时候把权值设置成相反数

              1
            /*
            --------------------------------------------------------------------------------------
            */
              2
              3 #include <algorithm>
  4 #include <iostream>
  5 #include <cstring>
  6 #include <ctype.h>
  7 #include <cstdlib>
  8 #include <cstdio>
  9 #include <vector>
 10 #include <string>
 11 #include <queue>
 12 #include <stack>
 13 #include <cmath>
 14 #include <set>
 15 #include <map>
 16 17//debug function for a N*M array 18#define debug_map(N,M,G) printf("\n");for(int i=0;i<(N);i++) 19 {for(int j=0;j<(M);j++){ 20 printf("%d",G[i][j]);}printf("\n");}
 21//debug function for int,float,double,etc. 22#define debug_var(X) cout<<#X"="<<X<<endl;
 23#define LL long long
 24constint INF = 0x3f3f3f3f;
 25const LL LLINF = 0x3f3f3f3f3f3f3f3f;
 26/*--------------------------------------------------------------------------------------*/ 27usingnamespace std;
 28 29int N,M,T;
 30constint maxn = 310;
 31int nx,ny;
 32int g[maxn][maxn];
 33int linker[maxn],lx[maxn],ly[maxn];
 34int slack[maxn];
 35bool visx[maxn],visy[maxn];
 36bool DFS(int x)
 37{
 38     visx[x] = true;
 39for(int y=0;y<ny;y++)
 40    {
 41if(visy[y]) continue;
 42int tmp = lx[x] + ly[y] - g[x][y];
 43if(tmp == 0)
 44        {
 45             visy[y] = true;
 46if(linker[y] == -1 || DFS(linker[y]))
 47            {
 48                 linker[y] = x;
 49returntrue;
 50            }
 51        }
 52elseif(slack[y] > tmp) slack[y] = tmp;
 53    }
 54returnfalse;
 55}
 56int KM()
 57{
 58     memset(linker,-1,sizeof linker);
 59     memset(ly,0,sizeof ly);
 60for(int i=0;i<nx;i++)
 61    {
 62         lx[i] = -INF;
 63for(int j=0;j<ny;j++)   lx[i] = max(lx[i],g[i][j]);
 64    }
 65for(int x=0;x<nx;x++)
 66    {
 67for(int i=0;i<ny;i++) slack[i] = INF;
 68while(true)
 69        {
 70             memset(visx,false,sizeof visx);
 71             memset(visy,false,sizeof visy);
 72if(DFS(x)) break;
 73int d = INF;
 74for(int i=0;i<ny;i++) if(!visy[i] && d > slack[i]) d = slack[i];
 75for(int i=0;i<nx;i++) if(visx[i]) lx[i] -= d;
 76for(int i=0;i<ny;i++)
 77            {
 78if(visy[i]) ly[i] += d;
 79else slack[i] -= d;
 80            }
 81        }
 82    }
 83int res = 0;
 84for(int i=0;i<ny;i++) if(linker[i] != -1) res += g[linker[i]][i];
 85return res;
 86}
 87int main()
 88{
 89while(~scanf("%d",&N))
 90    {
 91for(int i=0;i<N;i++)
 92        {
 93for(int j=0;j<N;j++)
 94            {
 95                 scanf("%d",&g[i][j]);
 96            }
 97        }
 98         nx = ny = N;
 99         printf("%d\n",KM());
100    }
101 }

 

原文：http://www.cnblogs.com/helica/p/5829491.html

内容总结

以上是互联网集市为您收集整理的HDU2255-奔小康赚大钱-二分图最大权值匹配-KM算法全部内容，希望文章能够帮你解决HDU2255-奔小康赚大钱-二分图最大权值匹配-KM算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1074776.html

来源：【匿名】