英语课件做的好的网站,上海浦东注册公司,html5软件下载官网,企业注册公司流程转载请注明出自cxb:http://blog.csdn.net/cxb569262726 题目链接#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid1533 说实话#xff0c;这个题目刚开始还真看不出是完备匹配下的最大权匹配#xff08;当然#xff0c;这个也可以用网络流做。#xff08;应该是添加…转载请注明出自cxb:http://blog.csdn.net/cxb569262726 题目链接http://acm.hdu.edu.cn/showproblem.php?pid1533 说实话这个题目刚开始还真看不出是完备匹配下的最大权匹配当然这个也可以用网络流做。应该是添加源点、汇点源点到每个m的距离取m到所有H中最小的那个用一个大数减掉后就是最大的汇点到每个H的距离类似然后求最大流 有空再试着做一下吧空说无益。 我是在图论500题里看到的在网络流基础题里面。一开始想不出这个怎么流 后面网上查这个是二分图最优匹配。于是昨天花几个小时看了相关资料写了个比这题更水的 HDU2255。 今天写这题的时候明显轻松了。而且还想到用网络流的做法。发现网络流和二分匹配还是有联系的。 下面直接贴代码吧看不懂的可以先看http://blog.csdn.net/cxb569262726/article/details/7871313 #includecstdio
#includecstring
#includeiostream
#includecmath
#includecstdlib
#includeclimits
#define MAXN 105
using namespace std;int n,m,numm,numh;
int map[MAXN][MAXN],lx[MAXN],ly[MAXN],vx[MAXN],vy[MAXN],matchy_x[MAXN];
char s[MAXN][MAXN];
int abs(int a){return a0?-a:a;}bool hungary(int u)
{int i;vx[u]1;for(i0;inumm;i){if(vy[i] || map[u][i]!lx[u]ly[i]) continue;vy[i]1;if(matchy_x[i]-1 || hungary(matchy_x[i])){matchy_x[i]u;return 1;}}return 0;
}void EK_match()
{int i,j;for(i0;inumm;i){int maxx0;for(j0;jnumh;j)if(map[i][j]maxx) maxxmap[i][j];lx[i]maxx;}for(i0;inumm;i){while(1){memset(vx,0,sizeof(vx));memset(vy,0,sizeof(vy));if(hungary(i))break;else{int tempINT_MAX;for(j0;jnumm;j) if(vx[j])for(int k0;knumh;k) if(!vy[k] templx[j]ly[k]-map[j][k])templx[j]ly[k]-map[j][k];for(j0;jnumm;j){if(vx[j]) lx[j]-temp;if(vy[j]) ly[j]temp;}}}}
}int main()
{int i,j;while(scanf(%d%d,n,m)!EOF (n||m)){for(i0;in;i) scanf(%s,s[i]);numm0;for(i0;in;i){for(j0;jm;j){if(s[i][j]m){numh0;for(int k0;kn;k){for(int l0;lm;l){if(s[k][l]H)map[numm][numh]300-(abs(i-k)abs(j-l));}}numm;}}}memset(matchy_x,-1,sizeof(matchy_x));EK_match();int ans0;for(i0;inumm;i)ans(300-map[matchy_x[i]][i]);printf(%d\n,ans);}return 0;
} 以下是slack数组优化的 #includecstdio
#includecstring
#includeiostream
#includecmath
#includecstdlib
#includeclimits
#define MAXN 105
using namespace std;int n,m,numm,numh;
int map[MAXN][MAXN],lx[MAXN],ly[MAXN],vx[MAXN],vy[MAXN],matchy_x[MAXN],slack[MAXN];
char s[MAXN][MAXN];
int abs(int a){return a0?-a:a;}
int min(int a,int b) {return ab?a:b;}bool hungary(int u)
{int i;vx[u]1;for(i0;inumm;i){if(vy[i]) continue;if(map[u][i]lx[u]ly[i]){vy[i]1;if(matchy_x[i]-1 || hungary(matchy_x[i])){matchy_x[i]u;return 1;}}else slack[i]min(slack[i],lx[u]ly[i]-map[u][i]);}return 0;
}void EK_match()
{int i,j;for(i0;inumm;i){int maxx0;for(j0;jnumh;j)if(map[i][j]maxx) maxxmap[i][j];lx[i]maxx;}for(i0;inumm;i){memset(slack,127,sizeof(slack));while(1){memset(vx,0,sizeof(vx));memset(vy,0,sizeof(vy));if(hungary(i))break;else{int tempINT_MAX;for(j0;jnumm;j) if(!vy[j])if(tempslack[j]) tempslack[j];for(j0;jnumm;j){if(vx[j]) lx[j]-temp;if(vy[j]) ly[j]temp;else slack[j]-temp;}}}}
}int main()
{int i,j;while(scanf(%d%d,n,m)!EOF (n||m)){for(i0;in;i)scanf(%s,s[i]);numm0;for(i0;in;i){for(j0;jm;j){if(s[i][j]m){numh0;for(int k0;kn;k){for(int l0;lm;l){if(s[k][l]H)map[numm][numh]300-(abs(i-k)abs(j-l));}}numm;}}}memset(matchy_x,-1,sizeof(matchy_x));EK_match();int ans0;for(i0;inumm;i)ans(300-map[matchy_x[i]][i]);printf(%d\n,ans);}return 0;
}ok睡觉吧。。明天比赛~~~ Good luck 转载于:https://www.cnblogs.com/javaspring/archive/2012/08/16/2656035.html
