二分图最大权完美匹配

二分图最大权完美匹配

思想

根据 大牛博客 改编

注意前提是二分图存在完美匹配

核心思想: 调整思想

讲算法之前先问个问题: 如果你要结婚,你会选择你爱的还是爱你的?(请各位直男以girl的角度回答)

相信大部分人的回答都是找一个爱自己多一点的。至于为什么…爱过你就知道了。

那么问题来了,我们如何高效的找出一种匹配方法,使得每个女孩都能尽可能的被爱自己更多的人在一起?

如图,每条红线表示男生对女生的喜欢程度。 女生左边的数字是她们心里的期望。(即男生对她最大的喜欢程度) 男生右边的数字是他们的自我膨胀指数(后面会解释)。

问题搞清楚了,那么怎么找呢?

首先,要理解这个算法,必须先明白几个道理:

(如果你是从二分图匹配看下来的,那么你会发现接下来的男女和讲二分图匹配的时候顺序反了过了。只是因为网上的图是这么给的,所以就这么讲了。(其实是因为我有一颗男女平等的心))

  1. 女生都有一颗不过分的舍己为人的心 (同二分图最大匹配)
  2. 女生在选男朋友的时候,只要这个男朋友满足她心里的期望,她就会选择他。 原因是:女生不傻,她的期望一定是在可满足范围内最高的,即总会存在至少一个男生满足她的心理期望。
  3. 男生也是人,也有自尊。

如果现在只有林俊杰和我同时喜欢徐佳莹,但是我对徐佳莹的喜欢有5分,林俊杰对她的喜欢只有3分。那么徐佳莹的心理期望肯定是5分,肯定也会选我作为她的男盆友 (๑•̀ㅂ•́)و✧

徐佳莹选完之后,张碧晨开始选。她发现所有男生里只有我喜欢她,所以她不得不选我。但是因为我之前被徐佳莹选走了,抱着一颗舍己为人的心,徐佳莹只能重新选择林俊杰。所以徐佳莹的心理期望必须要由5降到3。那我就开始膨胀了,毕竟现在我是抢手货了,我的膨胀指数就会相应的增加2(后面有解释)。(可把我牛逼坏了,叉会腰<( ̄︶ ̄)>)。我一膨胀,那么碧晨的期望值就要下降(毕竟哥哥我现在是抢手货,肯定不能像以前一样宠着她了),那么她的心理期望就应该成为: 我原来对她的喜欢程度 - 我的膨胀指数。

为什么增加2 :可以从两个方面理解

一: 本来我对徐佳莹需要五分的喜欢,她才会选我。现在她的期望变成了三,所以只要三分就可以了。我就会觉得我的个人魅力(膨胀指数)提高了两分。(应该蛮好理解的吧,如果还是不理解…先去谈恋爱吧)

二: 参考接下来的第4条。

  1. 那么现在我们可以知道女生选择男朋友的条件实际上是: 心理期望 == 该男生对她原本的喜欢程度 - 该男生的膨胀指数

算法的原理其实和二分图最大匹配的原理差不多,只不过多出来了期望值和自我膨胀指数这两个东西。所以在每次无法成功找到匹配的时候都要相应的去减少女生的期望和增加男生的膨胀指数,然后再重新匹配,直到匹配成功为止,因为图本身就是完全图,所以一定会有解。

需要注意的是,为了保证所求的结果是最大的。 我们在女生降低期望时希望降低的尽可能小,于是这里用一个slack数组维护: 当一个女生需要重新选择时,她所需要降低的最小期望值。 同时,这个值也是男生所增加的膨胀值。

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// 复杂度 O(nx * nx * ny)
// x - girl , y - boy
// lx - 心理期望 ly - 膨胀指数
// slack - 女生心理期望降低的最小程度 或 男生膨胀指数增加的最小程度
int nx,ny;
int G[maxn][maxn];
int linker[maxn],lx[maxn],ly[maxn];
int slack[maxn];
bool visx[maxn],visy[maxn];

void addedge(int i,int k,int w){
G[i][k] = w;
}

bool dfs(int x) {
visx[x] = true;
for (int y = 0; y < ny; y++) {
if (visy[y]) continue;
int temp = lx[x] + ly[y] - G[x][y]; //心理期望与男生实际喜欢自己程度的差值
if (temp == 0) { // 该男生满足心理期望
visy[y] = true;
if (linker[y] == -1 || dfs(linker[y])) {
linker[y] = x;
return true;
}
} else if (slack[y] > temp) //不满足心理期望,记录女生需要降低多少心理期望
slack[y] = temp;
}
return false;
}

int KM() {
memset(linker, -1, sizeof(linker));
memset(ly, 0, sizeof(ly)); //一开始男生一点都不膨胀
for (int i = 0; i < nx; i++) {
lx[i] = NINF;
for (int k = 0; k < ny; k++) {
if (G[i][k] > lx[i]) {
lx[i] = G[i][k];
}
}
}
for (int x = 0; x < nx; x++) {
for (int i = 0; i < ny; i++) slack[i] = INF;
while (true) {
memset(visx, 0, sizeof(visx));
memset(visy, 0, sizeof(visy));
if (dfs(x)) break; // 如果x女生匹配成功则退出
int d = INF;
for (int i = 0; i < ny; i++) {
if (!visy[i] && d > slack[i]) d = slack[i]; // 记录x女生需要降低的最小期望值
}
for (int i = 0; i < nx; i++) {
if (visx[i]) lx[i] -= d;
}
for (int i = 0; i < ny; i++) {
if (visy[i])
ly[i] += d; //女生期望降低对应着某些男性的膨胀
else
slack[i] -= d; //因为女生的心理期望降低了,所以该女生和其它备胎之间的差值也会缩小
}
}
}
int res = 0;
for (int i = 0; i < ny; i++) {
if (linker[i] != -1) res += G[linker[i]][i];
}
return res;
}
Thank you for your support!