沒怎么理解。。。過段時間再看看

轉自點擊打開鏈接

【KM算法及其具體過程】

（2）KM 算法的核心思想就是通過修改某些點的標號（但要滿足點標始終是可行的），不斷增加圖中的可行邊總數，直到圖中存在僅由可行邊組成的完全匹配為止，此時這個 匹配一定是最佳的（因為由可行點標的的定義，圖中的任意一個完全匹配，其邊權總和均不大于所有點的標號之和，而僅由可行邊組成的完全匹配的邊權總和等于所 有點的標號之和，故這個匹配是最佳的）。一開始，求出每個點的初始標號：lx[i]=max{e.W|e.x=i}（即每個X方點的初始標號為與這個X方 點相關聯的權值最大的邊的權值），ly[j]=0（即每個Y方點的初始標號為0）。這個初始點標顯然是可行的，并且，與任意一個X方點關聯的邊中至少有一條可行邊；

（6）以上就是KM算法的基本思路。但是樸素的實現方法，時間復雜度為O(n4)——需要找O(n)次增廣路，每次增廣最多需要修改O(n)次頂標，每次修改頂 標時由于要枚舉邊來求d值，復雜度為O(n2)。實際上KM算法的復雜度是可以做到O(n3)的。我們給每個Y頂點一個“松弛量”函數slack，每次開 始找增廣路時初始化為無窮大。在尋找增廣路的過程中，檢查邊(i,j)時，如果它不在相等子圖中，則讓slack[j]變成原值與 A[i]+B[j]-w[i,j]的較小值。這樣，在修改頂標時，取所有不在交錯樹中的Y頂點的slack值中的最小值作為d值即可。但還要注意一點：修 改頂標后，要把所有不在交錯樹中的Y頂點的slack值都減去d

代碼：

#include<bits/stdc++.h>using namespace std;const int maxn = 305;const int INF = 0x3f3f3f3f;int n, nx, ny;int match[maxn], lx[maxn], ly[maxn], slack[maxn];   ////lx,ly為頂標，nx,ny分別為x點集y點集的個數int visx[maxn], visy[maxn], w[maxn][maxn];int Hungary(int x){    visx[x] = 1;    for(int y = 1; y <= ny; y++)    {        if(visy[y]) continue;        int temp = lx[x]+ly[y]-w[x][y];        if(temp == 0)        {            visy[y] = 1;            if(match[y] == -1 || Hungary(match[y]))            {                match[y] = x;                return 1;            }        }        else if(slack[y] > temp)    ////不在相等子圖中slack 取最小的            slack[y] = temp;    }    return 0;}int KM(){    memset(match, -1, sizeof(match));    memset(ly, 0, sizeof(ly));    for(int i = 1; i <= nx; i++)        lx[i] = -INF;    for(int i = 1; i <= nx; i++)    // //lx初始化為與它關聯邊中最大的        for(int j = 1; j <= ny; j++)            if(w[i][j] > lx[i])                lx[i] = w[i][j];    for(int x = 1; x <= nx; x++)    {        for(int i = 1; i <= ny; i++)            slack[i] = INF;        while(1)        {            memset(visx, 0, sizeof(visx));            memset(visy, 0, sizeof(visy));            if(Hungary(x)) break;   ////若成功（找到了增廣軌），則該點增廣完成，進入下一個點的增廣                         //若失敗（沒有找到增廣軌），則需要改變一些點的標號，使得圖中可行邊的數量增加。                        //方法為：將所有在增廣軌中（就是在增廣過程中遍歷到）的X方點的標號全部減去一個常數d，                        //所有在增廣軌中的Y方點的標號全部加上一個常數d            int d = INF;            for(int i = 1; i <= ny; i++)                if(!visy[i] && d > slack[i])                    d = slack[i];            for(int i = 1; i <= nx; i++)                if(visx[i])                    lx[i] -= d;            for(int i = 1; i <= ny; i++)                if(visy[i])                    ly[i] += d;                else                    slack[i] -= d;        }    }    int res = 0;    for(int i = 1; i <= ny; i++)        if(match[i] != -1)            res += w[match[i]][i];    return res;}int main(void){    while(cin >> n)    {        nx = ny = n;        for(int i = 1; i <= n; i++)            for(int j = 1; j <= n; j++)                scanf("%d", &w[i][j]);        int ans = KM();        PRintf("%d/n", ans);    }    return 0;}
傳說在遙遠的地方有一個非常富裕的村落,有一天,村長決定進行制度改革：重新分配房子。 這可是一件大事,關系到人民的住房問題啊。村里共有n間房間,剛好有n家老百姓,考慮到每家都要有房住（如果有老百姓沒房子住的話，容易引起不安定因素），每家必須分配到一間房子且只能得到一間房子。 另一方面,村長和另外的村領導希望得到最大的效益,這樣村里的機構才會有錢.由于老百姓都比較富裕,他們都能對每一間房子在他們的經濟范圍內出一定的價格,比如有3間房子,一家老百姓可以對第一間出10萬,對第2間出2萬,對第3間出20萬.(當然是在他們的經濟范圍內).現在這個問題就是村領導怎樣分配房子才能使收入最大.(村民即使有錢購買一間房子但不一定能買到,要看村領導分配的). Input輸入數據包含多組測試用例，每組數據的第一行輸入n,表示房子的數量(也是老百姓家的數量)，接下來有n行,每行n個數表示第i個村名對第j間房出的價格(n<=300)。 Output請對每組數據輸出最大的收入值，每組的輸出占一行。 Sample Input
2100 1015 23Sample Output
123