原文鏈接http://www.cnblogs.com/zhouzhendong/p/8284105.html

---

題目傳送門 - HDU2853

---

題意概括

（來自谷歌翻譯）

---

題解

　　這是一道好題。

　　我們首先把所有邊權都乘上(n+1)。

　　然后對于原來就有的邊，我們再+1.

　　然后跑一跑KM，利用的原邊數就是ans%(n+1)，最終方案的效果就是ans/(n+1)

　　為什么是對的？

　　考慮1和n+1差距很大。

　　事實上，原來的邊權看作第一關鍵字，然后是否選用原邊看作第二關鍵字，然后通過給第一關鍵字乘一個較大的數來巧妙的KM求解。

---

代碼

#include <cstring> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cmath> using namespace std; const int N=55,Inf=1e9+7; int n,m,g[N][N],ex[N],ey[N],match[N],minadd[N]; bool visx[N],visy[N]; bool Match(int x){visx[x]=1;for (int i=1;i<=m;i++)if (!visy[i]){int add=ex[x]+ey[i]-g[x][i];if (!add){visy[i]=1;if (!match[i]||Match(match[i])){match[i]=x;return 1;}}elseminadd[i]=min(minadd[i],add);}return 0; } int KM(){memset(match,0,sizeof match);memset(ey,0,sizeof ey);for (int i=1;i<=n;i++){ex[i]=g[i][1];for (int j=2;j<=m;j++)ex[i]=max(ex[i],g[i][j]);}for (int i=1;i<=n;i++){for (int j=1;j<=m;j++)minadd[j]=Inf;while (1){memset(visx,0,sizeof visx);memset(visy,0,sizeof visy);if (Match(i))break;int delta=Inf;for (int j=1;j<=m;j++)if (!visy[j])delta=min(delta,minadd[j]);for (int j=1;j<=n;j++)if (visx[j])ex[j]-=delta;for (int j=1;j<=m;j++)if (visy[j])ey[j]+=delta;elseminadd[j]-=delta;}}int ans=0;for (int i=1;i<=m;i++)if (match[i])ans+=g[match[i]][i];return ans; } int main(){while (~scanf("%d%d",&n,&m)){for (int i=1;i<=n;i++)for (int j=1;j<=m;j++){scanf("%d",&g[i][j]);g[i][j]*=n+1;}int pre_val=0;for (int i=1,x;i<=n;i++){scanf("%d",&x);pre_val+=g[i][x]/(n+1);g[i][x]++;}int ans=KM();printf("%d %d\n",n-ans%(n+1),ans/(n+1)-pre_val);}return 0; }

　　

?

轉載于:https://www.cnblogs.com/zhouzhendong/p/HDU2853.html

總結

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

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