本文主要是介绍poj 2400 Supervisor, Supervisee，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
有n个工人（老板），他们给自己想要的老板（工人）排名。求出所有最佳组合
KM+DFS().求出来最小值后把所有可能搭配DFS一遍就可以得出满足要求的搭配了。
#include<stdio.h>
#include<string.h>
#define inf 1000000
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
int ans;
int t,n,x,tot,sum;
int map[16][16],lx[16],ly[16],visx[16],visy[16],check[20],link[16];
bool match(int i)
{
visx[i]=1;
for(int j=1;j<=n;j++)
{
if(visy[j]==0&&lx[i]+ly[j]-map[i][j]==0)
{
visy[j]=1;
if(link[j]==-1||match(link[j]))
{
link[j]=i;
return true;
}
}
}
return false;
}
int km()
{
for(int i=1;i<=n;i++)
{
lx[i]=-inf;
for(int j=1;j<=n;j++)
lx[i]=max(lx[i],map[i][j]);
}
memset(ly,0,sizeof(ly));
memset(link,-1,sizeof(link));
for(int i=1;i<=n;i++)
{
while(1)
{
memset(visx,0,sizeof(visx));
memset(visy,0,sizeof(visy));
if(match(i)) break;
int d=inf;
for(int j=1;j<=n;j++)
{
if(visx[j]==1)
for(int k=1;k<=n;k++)
if(visy[k]==0)
d=min(d,lx[j]+ly[k]-map[j][k]);
}
for(int j=1;j<=n;j++)
{
if(visx[j]==1) lx[j]-=d;
if(visy[j]==1) ly[j]+=d;
}
}
}
ans=0;
for(int i=1;i<=n;i++)
ans-=map[link[i]][i];
return ans;
}
void dfs(int dept,int sum)
{
if(sum>ans) return;
if(dept>n)
{
if(sum!=ans) return;
printf("Best Pairing %d\n",++tot);
for(int i=1;i<=n;i++)
printf("Supervisor %d with Employee %d\n",i,link[i]);
}
else
{
for(int i=1;i<=n;i++)
{
if(check[i]==0)
{
check[i]=1;
link[dept]=i;
dfs(dept+1,sum-map[dept][i]);
check[i]=0;
}
}
}
}
int main()
{
scanf("%d",&t);
for(int tt=1;tt<=t;tt++)
{
scanf("%d",&n);
tot=0;
memset(map,0,sizeof(map));
for(int i=1;i<=n;i++)
for(int j=0;j<n;j++)
{
scanf("%d",&x);
map[x][i]-=j;
}
for(int i=1;i<=n;i++)
for(int j=0;j<n;j++)
{
scanf("%d",&x);
map[i][x]-=j;
}
printf("Data Set %d, Best average difference: %.6f\n",tt,km()/(2.00000*n));
memset(check,0,sizeof(check));
dfs(1,0);
printf("\n");
}
return 0;
}这篇关于poj 2400 Supervisor, Supervisee的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
