來自網上的巧妙思路：

因為我們要變動最小，所以對在原計劃中的邊要有一些特殊照顧，使得最優匹配時，盡量優先使用原計劃的邊，這樣變化才能是最小的且不會影響原匹配。

根據這個思想，我們可以把每條邊的權值擴大k倍，k要大于n。然后對原計劃的邊都+1。精華全在這里。我們來詳細說明一下。

全部邊都擴大了k倍，而且k比n大，這樣，我們求出的最優匹配就是k倍的最大權值，只要除以k就可以得到最大權值。實現原計劃的邊加1，這樣，在每次選擇邊時，這些變就 有了優勢，就會優先選擇這些邊。假如原計劃的h條邊被選入了最優匹配中，這樣，最優權值就是k倍的最大權值+k（原計劃的每條邊都+1）。但是k大于n的用意何在呢？我們發現假如原計劃的邊全部在匹配中，只會增加n，又n<k,所以除以k后不會影響最優匹配的最大權值之和，然后我們對k取余，就正好得到加入的原計劃的邊的個數。這時，我們只需要用總點數-加入的原計劃的點數，就可以求得最小變動數了。

//#pragma comment(linker, "/STACK:102400000,102400000") #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> using namespace std; typedef long long LL; const long long mod = 1e9 + 7; const int INF = 0x3f3f3f3f; const int M = 305;/*求最大權匹配 若求最小全匹配,可將權值取相反數,結果取相反數*/int nx, ny; //兩邊的點數 int g[M][M]; //二分圖描述 int link[M], lx[M], ly[M]; //y中各點匹配狀態,x,y中的點編號 int slack[M]; bool visx[M], visy[M];bool dfs(int x) {visx[x] = 1;for (int y = 1; y<=ny; y++){if (visy[y])continue;int tmp = lx[x] + ly[y] - g[x][y];if (!tmp){visy[y] = 1;if (link[y] == -1 || dfs(link[y])){link[y] = x;return 1;}}else if (slack[y]>tmp) //不在相等子圖中slack 取最小的{slack[y] = tmp;}}return 0; }int KM() {memset(link, -1, sizeof(link));memset(ly, 0, sizeof(ly));for (int i = 1; i<=nx; ++i) //lx,ly為頂標，nx,ny分別為x點集y點集的個數{lx[i] = -INF;for (int j = 1; j<=ny; ++j){if (g[i][j]>lx[i]){lx[i] = g[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 (dfs(x)) //若成功（找到了增廣軌），則該點增廣完成，進入下一個點的增廣break; //若失敗（沒有找到增廣軌），則需要改變一些點的標號，使得圖中可行邊的數量增加。//方法為：將所有在增廣軌中（就是在增廣過程中遍歷到）的X方點的標號全部減去一個常數d，//所有在增廣軌中的Y方點的標號全部加上一個常數dint 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) //修改頂標后，要把所有不在交錯樹中的Y頂點的slack值都減去d{if (visy[i])ly[i] += d;elseslack[i] -= d;}}}int res = 0;for (int i = 1; i<=ny; ++i){if (link[i] != -1)res += g[link[i]][i];}return res; }int main() {int n,m;while (~scanf("%d%d", &n, &m)){memset(g,0,sizeof(g));for (int i = 1; i<=n; ++i){for (int j = 1; j<=m; ++j){scanf("%d", &g[i][j]);g[i][j] *= 100;}}int ans=0;for (int i = 1; i<=n; ++i){int tmp;scanf("%d",&tmp);ans+=g[i][tmp];g[i][tmp]+=1;}nx=n;ny=m;int res=KM();printf("%d %d\n", n - res % 100, res / 100 - ans / 100);}return 0; }

總結

以上是生活随笔為你收集整理的HDU 2853 Assignment （KM算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。