原文链接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的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。