二分图最佳匹配
8616 汽车拉力比赛
8616 汽车拉力比赛
时间限制:500MS 内存限制:1000K
提交次数:3 通过次数:3
题型: 编程题 语言: 无限制
描述
SCAU车队要去参加汽车拉力比赛啦。拉力比赛中，每辆汽车需要一个驾驶员和一个导航员。SCAU车队一共有有N个驾驶员和N个导航员，每个 驾驶员对每个导航员有一个默契值，现在需要求得某种N对N的配对，使得这N个配对的默契值之和最大。Input
多Case，每一个Case第一行是一个整数N,范围是(1<=N<=16)。接下来有N行，每行有N个数，第i行第j个数表示第i个驾驶员和第j个导航员的默契值。 测试数据会有多组，当N=0时表示数据结束，这行不用处理。Output
输出配对后默契值之和的最大值。
Sample Input
1 5 2 10 20 25 5 0
Sample Output
5 45
Source
CPP 这题很明显的二分图最佳匹配，很显然我不会，果断去找资料，经过理解和研究标程，已经将其纳为己用了，这就是传说中的km算法，理解有点蛋疼，因为老说什么交错树，不知道是什么东东，不过不鸟它，看代码直接自己想能想通的，下面是我的代码。。。#include<string>
#include<algorithm>
#define N 100
using namespace std;
int gp[N][N],vx[N],vy[N],fx[N],fy[N],n,m[N];
int dfs(int u)
{vx[u]=1;for(int i=0;i<n;i++){if(vy[i]==0&&fx[u]+fy[i]==gp[u][i]){vy[i]=1;if(m[i]==-1||dfs(m[i])){m[i]=u;return 1;}}}return 0;
}
int count()
{int i,j,k,d,ans;for(i=0;i<n;i++){fx[i]=-0x7fffffff;fy[i]=0;for(j=0;j<n;j++){if(fx[i]<gp[i][j]){fx[i]=gp[i][j];}}}memset(m,-1,sizeof(m));for(int u=0;u<n;u++){memset(vx,0,sizeof(vx));memset(vy,0,sizeof(vy));while(!dfs(u)){d=0x7fffffff;for(i=0;i<n;i++){if(vx[i])for(j=0;j<n;j++){if(!vy[j]){if(d>(fx[i]+fy[j]-gp[i][j]))d=fx[i]+fy[j]-gp[i][j];}}}for(i=0;i<n;i++){if(vx[i])fx[i]-=d,vx[i]=0;if(vy[i])fy[i]+=d,vy[i]=0;}}}ans=0;for(i=0;i<n;i++){ans+=gp[m[i]][i];}return ans;
}
int main()
{int i,j;while(1){scanf("%d",&n);if(n==0)return 0;for(i=0;i<n;i++)for(j=0;j<n;j++){scanf("%d",&gp[i][j]);}printf("%d\n",count());}return 0;
}更多推荐
二分图最佳匹配
发布评论