Code 備忘錄►Graph

TIOJ::1042 . E.老問題

二分圖最大權匹配，KM演算法。

這題之前一直覺得很難懂，一定都是網路上的講解太複雜了(哼!?)，雖然匈牙利系列的演算法就是很難懂啦!!!

參考連結：
http://www.twwiki.com/wiki/KM%E6%BC%94%E7%AE%97%E6%B3%95
code倉庫 - 可以看CBD的code應該比我的好讀

重點就是KM演算法!!!!
KM演算法有分成 一般N^4 和 N^3 兩種，可是我試了N^3結果比N^4慢兩倍= =。
總覺得是因為N才100真的太小，N^3增加的常數還比較大。

這種匈牙利系列的演算法特色就是code很短，懂了之後很簡單，可是很難懂。

首先，你要先會匈牙利演算法。

好了，KM演算法就是把二分圖最大權匹配問題，轉換成二分圖完美匹配問題的一種演算法。

先設定一個東西，大部分人都稱他為「頂標」。

把二分圖分成X(女生)跟Y(男生)，分別代表二分圖的兩邊點集合。其中每個點都有一個頂標，可以把它當成點的權重。
在任何的時候，對於每一條邊(戀情)，他的兩端點的頂標和，一定要大於等於邊的權重(美滿程度)，這是我們設定好的。

一開始，我們先把每個Y頂標設定成0，X頂標設定成那個點到Y集合裡的點中，邊權最大的(那個女生最喜歡的男生)。(也可以反過來，X頂標都是0，Y頂標是最大邊權，二分圖基本上來說，XY對調都可以。)

然後，我們做匈牙利，找出完美匹配，但是我們不是對每條邊做，而是對「兩端點頂標和等於邊權」的邊做。
對，我們發現，一開始這些邊就是每個X點連到Y點中最大的那幾條邊(那個女生最喜歡的男生)，如果可以順利匹配，那我們就做完了，但是很不幸的，一定有X的最大邊連到的Y是同一個Y。(兩個女的最喜歡同一個男的。)

這時候怎麼辦，當然是犧牲其中一個人叫他去找別人啦。但是要找誰呢?
當然是機會成本最小的！
這就是KM的精華。
我們先找出機會成本，假設每一個女生跟他沒看上的男生(兩端點頂標和不等於邊權的邊)交往，會損失的美滿度(頂標和 - 邊權)當作機會成本，我們當然希望機會成本越小越好。
所以機會成本就是上面考慮的值中最小的。
然後我們對頂標做一個操作，
把所有參加配對的女生(X)頂標減掉 機會成本，那些被喜歡的男生(Y)頂標加上 機會成本。

這樣操作完之後，我們發現很神奇的，原本考慮的那幾組配對(考慮的邊)因為一端加一端減，狀態不變，但是原本那些女生不喜歡的男生，因為頂標和變小(女生的標準降低?!)變得可以考慮了！
所以可能就變多了，我們可以再做一次匈牙利。

所以KM的流程就是
一個一個女生加入，然後這些女生開始選男生(做匈牙利)，如果吵架(匈牙利失敗)，就找出最小的機會成本然後降低女生的門檻，然後再做，直到女生們都找到男生了，再加入下一個女生，直到所有女生都加入了，我們就找到最完美的匹配了。

coding細節就是，
X頂標是X希望的匹配中最大的，Y頂標是0，對於每個X做匈牙利，如果失敗就修改頂標。
找機會成本是關鍵，
其實機會成本就是 頂標和 - 邊權，因為我們知道頂標和一定大於邊權(我們設定好了)。
但是不要考慮 頂標和 = 邊權 的邊，因為那沒有意義。
然後因為X是一個一個加入的，所以對於那些跟還沒加入的X有關的邊，我們也不用管。

到這裡如果你看得懂我說的(我到底在說什麼??!)，你就會明白KM就是不斷加入女生然後讓他們打架直到都找到男生再加入下一個女生的演算法(疑?)

如果你看不懂，讀一下code吧

2015/10/21

後來想想，頂標更新應該更新全部的X和沒去過的Y才對，不過不這樣做也不會影響正確性，因為X會自動放寬。這樣頂多多一次放寬（修改頂標）動作而已。

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
#include <bits/stdc++.h>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=0;i<n;i++)
using namespace std;
const int N = 101, INF = 2147483647;
int n,G[N][N],back[N],tagX[N],tagY[N];
bool visX[N],visY[N];
// 輸入優化
int gin(){
    char c;int x;
    while(c=getchar(),(c<'0'||c>'9')&&c!='-');
    bool flag=c=='-';
    x=flag?0:c-'0';
    while(c=getchar(),c>='0'&&c<='9')x=x*10+c-'0';
    return flag?(-x):x;
}
// 匈牙利
bool dfs(int now){
    visX[now] = true;
    F(n)if(tagX[now]+tagY[i] == G[now][i]){
        visY[i] = true;
        if(back[i]==-1 || !visX[back[i]]&&dfs(back[i])){
            back[i] = now;
            return true;
        }
    }
    return false;
}
main(){
    while(n=gin(),n){
        F(n)Fi(j,n){
            G[i][j]=gin();
            if(G[i][j]<0)G[i][j]=0;
        }
        memset(tagY,0,sizeof(tagY));
        F(n){
            tagX[i]=0;
            Fi(j,n)tagX[i]=max(tagX[i],G[i][j]);
        }
        memset(back,-1,sizeof(back));
        F(n){
            memset(visX,0,sizeof(visX));
            memset(visY,0,sizeof(visY));
            while(!dfs(i)){
                int cut=INF;
                // 找機會成本
                Fi(j,n)if(visX[j])Fi(k,n)if(!visY[k]){
                    cut = min(cut, tagX[j]+tagY[k]-G[j][k]);
                }
                // 操作頂標
                Fi(j,n){
                    if(visX[j])tagX[j] -= cut;
                    if(visY[j])tagY[j] += cut;
                }
                memset(visX,0,sizeof(visX));
                memset(visY,0,sizeof(visY));
                cut=INF;
            }
        }
        int ans = 0;
        F(n)ans+=G[back[i]][i];
        printf("%d\n",ans);
    }
}