HDU 2255 KM算法 二分图最大权值匹配
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了HDU 2255 KM算法 二分图最大权值匹配，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2309字，纯文字阅读大概需要4分钟。
内容图文
奔小康赚大钱
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 10760 Accepted Submission(s): 4765
这可是一件大事,关系到人民的住房问题啊。村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住（如果有老百姓没房子住的话，容易引起不安定因素），每家必须分配到一间房子且只能得到一间房子。
另一方面,村长和另外的村领导希望得到最大的效益,这样村里的机构才会有钱.由于老百姓都比较富裕,他们都能对每一间房子在他们的经济范围内出一定的价格,比如有3间房子,一家老百姓可以对第一间出10万,对第2间出2万,对第3间出20万.(当然是在他们的经济范围内).现在这个问题就是村领导怎样分配房子才能使收入最大.(村民即使有钱购买一间房子但不一定能买到,要看村领导分配的).
1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 #include<algorithm>
5 #include<map>
6usingnamespace std;
7#define ll long long
8#define mod 998244353
9constint N=310;
10constint INF=0x3f3f3f3f;
11int nx,ny;
12int g[N][N];
13int linker[N],lx[N],ly[N];
14int slack[N];
15bool visx[N],visy[N];
16bool dfs(int x){
17 visx[x]=true;
18for(int y=0;y<ny;y++){
19if(visy[y]) continue;
20int tmp=lx[x]+ly[y]-g[x][y];
21if(tmp==0){
22 visy[y]=true;
23if(linker[y]==-1||dfs(linker[y])){
24 linker[y]=x;
25returntrue;
26 }
27 }elseif(slack[y]>tmp){
28 slack[y]=tmp;
29 }
30 }
31returnfalse;
32}
33int KM(){
34 memset(linker,-1,sizeof(linker));
35 memset(ly,0,sizeof(ly));
36for(int i=0;i<nx;i++){
37 lx[i]=-INF;
38for(int j=0;j<ny;j++){
39if(g[i][j]>lx[i]){
40 lx[i]=g[i][j];
41 }
42 }
43 }
44for(int x=0;x<nx;x++){
45for(int i=0;i<ny;i++)
46 slack[i]=INF;
47while(true){
48 memset(visx,false,sizeof(visx));
49 memset(visy,false,sizeof(visy));
50if(dfs(x)) break;
51int d=INF;
52for(int i=0;i<ny;i++){
53if(!visy[i]&&d>slack[i])
54 d=slack[i];
55 }
56for(int i=0;i<nx;i++){
57if(visx[i])
58 lx[i]-=d;
59 }
60for(int i=0;i<ny;i++){
61if(visy[i]) ly[i]+=d;
62else slack[i]-=d;
63 }
64 }
65}
66int res=0;
67for(int i=0;i<ny;i++){
68if(linker[i]!=-1)
69 res+=g[linker[i]][i];
7071 }
72return res;
73}
74int main(){
75int n;
76while(scanf("%d",&n)!=EOF){
77for(int i=0;i<n;i++){
78for(int j=0;j<n;j++){
79 scanf("%d",&g[i][j]);
80 }
81 }
82 nx=ny=n;
83 printf("%d\n",KM());
84 }
85return0;
86 }
原文：http://www.cnblogs.com/hsd-/p/7638547.html
内容总结
以上是互联网集市为您收集整理的HDU 2255 KM算法 二分图最大权值匹配全部内容，希望文章能够帮你解决HDU 2255 KM算法 二分图最大权值匹配所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。