本文主要是介绍ZOJ 2362 Beloved Sons，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
将男孩和女孩配对 让月老开心度最高 （我把题目改得真洋气…）
思路：
KM不解释…
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define oo 99999999
#define M 410
using namespace std;int t,n,m,ans;
int link[M],visx[M],visy[M],val[M][M],slack[M],x[M],y[M],fzc[M];int dfs(int now)
{int i,tmp;visx[now]=1;for(i=1;i<=n;i++){if(visy[i]) continue;tmp=x[now]+y[i]-val[now][i];if(tmp==0){visy[i]=1;if(link[i]==-1||dfs(link[i])){link[i]=now;return 1;}}else if(slack[i]>tmp) slack[i]=tmp;}return 0;
}void KM()
{int i,j,tmp;memset(link,-1,sizeof(link));memset(y,0,sizeof(y));for(i=1;i<=n;i++){x[i]=-oo;for(j=1;j<=n;j++){if(x[i]<val[i][j]) x[i]=val[i][j];}}for(i=1;i<=n;i++){for(j=1;j<=n;j++) slack[j]=oo;for(;;){memset(visx,0,sizeof(visx));memset(visy,0,sizeof(visy));if(dfs(i)) break;tmp=oo;for(j=1;j<=n;j++){if(!visy[j]&&tmp>slack[j]) tmp=slack[j];}for(j=1;j<=n;j++){if(visx[j]) x[j]-=tmp;}for(j=1;j<=n;j++){if(visy[j]) y[j]+=tmp;else slack[j]-=tmp;}}}
}int main()
{int i,j,k;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=1;i<=n;i++) scanf("%d",&fzc[i]);memset(val,0,sizeof(val));for(i=1;i<=n;i++){scanf("%d",&m);for(j=1;j<=m;j++){scanf("%d",&k);val[i][k]=fzc[i]*fzc[i];}}KM();memset(fzc,0,sizeof(fzc));for(i=1;i<=n;i++){if(link[i]!=-1 && val[link[i]][i]) fzc[link[i]]=i;}for(i=1;i<=n;i++) printf("%d%s",fzc[i],(i==n)?"\n":" ");if(t) printf("\n");}return 0;
}
这篇关于ZOJ 2362 Beloved Sons的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
