首页 > 编程语言 > 详细

KM算法模板 hdu 2255

时间:2019-09-16 21:01:00      阅读:96      评论:0      收藏:0      [点我收藏+]

KM算法是在匹配是完备的情况下寻找最优匹配。

首先,先将范围定为最大的情况,如果最大的情况无法满足,就下降一个维度继续匹配。

直到匹配成功。

 1 #include<cstdio>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn=3e2+10;
 6 const int inf=0x3f3f3f3f;
 7 int G[maxn][maxn],n;
 8 int lx[maxn],ly[maxn];
 9 int match[maxn];
10 int visx[maxn],visy[maxn];
11 void init()
12 {
13     memset(match,0,sizeof(match));
14 }
15 int dfs(int k)
16 {
17     visx[k]=1;
18     for(int i=1;i<=n;i++){
19         if(!visy[i]&&G[k][i]==lx[k]+ly[i]){
20             visy[i]=1;
21             if(!match[i]||dfs(match[i])){
22                 match[i]=k;
23                 return 1;
24             }
25         }
26     }
27     return 0;
28 }
29 int KM()
30 {
31     for(int i=1;i<=n;i++){
32         lx[i]=-inf,ly[i]=0;
33         for(int j=1;j<=n;j++)
34             lx[i]=max(lx[i],G[i][j]);
35     }
36     for(int k=1;k<=n;k++){
37         while(1){
38             memset(visx,0,sizeof(visx));
39             memset(visy,0,sizeof(visy));
40             if(dfs(k)) break;
41             int mn=inf;
42 
43             for(int i=1;i<=n;i++) if(visx[i])
44             for(int j=1;j<=n;j++) if(!visy[j])
45             mn=min(mn,lx[i]+ly[j]-G[i][j]);
46             if(mn==inf) return -1;
47             for(int i=1;i<=n;i++) if(visx[i]) lx[i]-=mn;
48             for(int i=1;i<=n;i++) if(visy[i]) ly[i]+=mn;
49         }
50     }
51     int ans=0;
52     for(int i=1;i<=n;i++) if(match[i])
53     ans+=G[match[i]][i];
54     return ans;
55 }
56 int main()
57 {
58     while(scanf("%d",&n)!=EOF){
59         init();
60         for(int i=1;i<=n;i++)
61         for(int j=1;j<=n;j++)
62         scanf("%d",&G[i][j]);
63         printf("%d\n",KM());
64     }
65     return 0;
66 }

 

KM算法模板 hdu 2255

原文:https://www.cnblogs.com/pangbi/p/11529469.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!