首页 > 代码库 > KM算法

KM算法

2024-11-03 01:04:02   203人阅读

啊呜啊呜，看来好几天的KM浸提终于弄懂了，前两天就一直看来着，然后看不明白，就放着了，今天不信，重拾KM终于磕会了。然后，其实好傻逼，就是匈牙利算法，加了一个+d   -d的过程

首先来看一个例子（hdu 2255 奔小康赚大钱）

题意：

1.村委会有n个人，n个房子

2.每个人可以为多个房子出不同的价钱

3.但是每个人只能发配到一个房子(必须每个人一个)

4.求出村委会能赚到最多的钱

 

(手动模拟一边，假如n=3)

技术分享

此时 x[n]=y[n]=0;

有个可以进行匹配的条件，就是 左边的值 + 右边的值 = 其连线的值

很显然，最开始  4+0=4  即 A 和 3进行匹配，所以

技术分享

 

 此时再次将 x[n]=y[n]=0;

然后为B 寻找匹配项，发现恰好 和3相加 能满足条件，但是呢，3此时已经和A匹配了 ，因为访问过B，3 ，所以 x[B]=1,y[3]=1;

现在看A能不能找到其他能满足的项，很显然没有，但是x[a]=1(因为被访问了)

此时就要寻找一个d (d 为 所有被访问过的人，即A,B 与未匹配过的房屋 即 1，2 中，左值右值之和与连线的差的最小值 )

于是找到此时的d为1，所以给u、所有匹配的人降低d ，所有匹配过的房增加d ,即

技术分享

此时，因为A可以找到一个匹配的房了，然后B 恰好也能找到与之相匹配的

 

 技术分享

 

 此时为C 寻找匹配项，发现并没有满足的，于是自减1

技术分享

首先x[n]=y[n]=0;（初始化为从未遍历过）

再次为C 寻找匹配项（x[C]=1），发现可以与3 （y[3]=1）进行匹配，但是3有了B ，让B寻找其他项（x[b]=1）,B可以与1匹配（y[1]=1）,但是1有了A，让A 寻找其他匹配（x[A]=1）

然而，并没有，，所以进行+d,-d这个操作，此时求得d=1；于是得到

技术分享

于是重复这个步骤

 技术分享

然后得到：

技术分享

然后，皆大欢喜，结束。。。。。。。。。

 

代码实现：

 1 #include<cstdio>
 2 #define Max 456
 3 #include<cstring>
 4 using namespace std;
 5 int g[Max][Max];
 6 int lx[Max],ly[Max];
 7 int visx[Max],visy[Max];
 8 int match[Max];
 9 int n;
10 int findpath(int u);
11 int KM();
12 int main()
13 {
14     //int T;
15     //scanf("%d",&T);
16     while(~scanf("%d",&n))
17     {
18         for(int i=1;i<=n;i++)
19         for(int j=1;j<=n;j++)
20         scanf("%d",&g[i][j]);
21         printf("%d\n",KM());
22     }
23     return 0;
24 }
25 int findpath(int u)
26 {
27     visx[u]=1;
28     for(int v=1;v<=n;v++)
29     {
30         if(!visy[v]&&lx[u]+ly[v]==g[u][v])
31         {
32             int t=match[v];visy[v]=1;
33             if(!t||findpath(t))
34             {
35                 match[v]=u;return 1;
36             }
37         }
38     }
39     return 0;
40 }
41 int KM()
42 {
43     for(int i=1;i<=n;i++)
44     {
45         lx[i]=0x80000000;
46         ly[i]=0;
47         for(int j=1;j<=n;j++)
48         if(lx[i]<g[i][j])
49         lx[i]=g[i][j];
50     }
51     memset(match,0,sizeof(match));
52     for(int u=1;u<=n;u++)
53     {
54         while(1)
55         {
56             memset(visx,0,sizeof(visx));
57             memset(visy,0,sizeof(visy));
58             if(findpath(u))
59             break;
60             int d=0x7fffffff;
61             for(int i=1;i<=n;i++)
62             {
63                 if(visx[i])
64                 {
65                     for(int j=1;j<=n;j++)
66                     if(!visy[j]&&d>lx[i]+ly[j]-g[i][j])
67                     d=lx[i]+ly[j]-g[i][j];
68                 }
69             }
70             for(int k=1;k<=n;k++)
71             {
72                 if(visx[k])
73                 lx[k]-=d;
74                 if(visy[k])
75                 ly[k]+=d;
76             }
77         }
78     }
79     int sum=0;
80     for(int i=1;i<=n;i++)
81     {
82         int t=match[i];
83         if(t)
84         sum+=g[t][i];
85     }
86     return sum;
87 }

 

KM算法


联系
我们