題目：http://acm.hdu.edu.cn/showproblem.php?pid=2853

二分圖的最優匹配。因為題目上的節點最多只有50個。所以先對所有權值*100，把原來各個匹配關系的權值+1，然后在求被改變的個數只需要 用 n-KM（）%100；就可以知道被改變的點的個數。最大的增量就用km()-pre_sum.即可。

下面是AC代碼：

#include<cstdio> #include<cstring> using namespace std; const int maxn = 1005; const int INF = (1<<30)-1; int g[maxn][maxn]; int lx[maxn],ly[maxn]; int match[maxn]; bool visx[maxn],visy[maxn]; int slack[maxn]; int n,m; bool dfs(int cur){visx[cur] = true;for(int y=1;y<=m;y++){if(visy[y]) continue;int t=lx[cur]+ly[y]-g[cur][y];if(t==0){visy[y] = true;if(match[y]==-1||dfs(match[y])){match[y] = cur;return true;}}else if(slack[y]>t){slack[y]=t;}}return false; } int KM(){memset(match,-1,sizeof(match));memset(ly,0,sizeof(ly));for(int i=1 ;i<=n;i++){lx[i]=-INF;for(int j=1;j<=m;j++)if(g[i][j]>lx[i]) lx[i]=g[i][j];}for(int x=1;x<=n;x++){for(int i=1;i<=m;i++) slack[i]=INF;while(true){memset(visx,false,sizeof(visx));memset(visy,false,sizeof(visy));if(dfs(x)) break;int d=INF;for(int i=1;i<=m;i++){if(!visy[i]&&d>slack[i]) d=slack[i];}for(int i=1;i<=n;i++){if(visx[i]) lx[i]-=d;}for(int i=1;i<=m;i++){if(visy[i]) ly[i]+=d;else slack[i]-=d;}}}int result = 0;for(int i = 1; i <=m; i++){if(match[i]>-1)result += g[match[i]][i];}return result; } int main(){int ca=1;int a,b,c;while(scanf("%d%d",&n,&m)!=EOF){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 pre_sum=0,sum;for(int i=1;i<=n;i++){scanf("%d",&a);pre_sum+=g[i][a];g[i][a]++;}sum=KM();printf("%d %d\n",n-sum%100,sum/100-pre_sum/100);}return 0; }

總結

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

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