題意：
給出職工對經理的評分和經理對職工的評分。求出所有的匹配方案，使得平均滿意度最高
解法:
KM匹配出最優解后，根據標號遍歷得所有解。注意，調整頂標以后合法匹配邊仍然是l[i]+r[j]=val[i][j]
代碼：
Source Code
| Problem: 2400 | | User: yzhw |
| Memory: 408K | | Time: 0MS |
| Language: G++ | | Result: Accepted |
# include <cstdio>
# include <cstring>
# include <cstdlib>
using namespace std;
# define max(a,b) ((a)>(b)?(a):(b))
# define min(a,b) ((a)<(b)?(a):(b))
# define N 15
int map[N][N],match[N],ln[N],rn[N],n,c;
bool l[N],r[N];
bool dfs(int pos)
{
l[pos]=true;
for(int i=0;i<n;i++)
if(!r[i]&&ln[pos]+rn[i]==map[pos][i])
{
r[i]=true;
if(match[i]==-1||dfs(match[i]))
{
match[i]=pos;
return true;
}
}
return false;
}
void adjust()
{
int minnum=0xfffffff;
for(int i=0;i<n;i++)
if(l[i])
for(int j=0;j<n;j++)
if(!r[j])
minnum=min(minnum,ln[i]+rn[j]-map[i][j]);
for(int i=0;i<n;i++)
{
if(l[i]) ln[i]-=minnum;
if(r[i]) rn[i]+=minnum;
}
}
void search(int now)
{
if(now==n)
{
int ret[N];
for(int i=0;i<n;i++)
ret[match[i]]=i;
printf("Best Pairing %d\n",++c);
for(int i=0;i<n;i++)
printf("Supervisor %d with Employee %d\n",i+1,ret[i]+1);
}
for(int i=0;i<n;i++)
if(match[i]==-1&&ln[now]+rn[i]==map[now][i])
{
match[i]=now;
search(now+1);
match[i]=-1;
}
}
int main()
{
int test;
scanf("%d",&test);
for(int tt=1;tt<=test;tt++)
{
scanf("%d",&n);
memset(map,0,sizeof(map));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
int t;
scanf("%d",&t);
map[t-1][i]-=j;
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
int t;
scanf("%d",&t);
map[i][t-1]-=j;
}
memset(match,-1,sizeof(match));
memset(rn,0,sizeof(rn));
for(int i=0;i<n;i++)
{
int maxnum=-0xfffffff;
for(int j=0;j<n;j++)
maxnum=max(maxnum,map[i][j]);
ln[i]=maxnum;
}
double ans=0;
for(int i=0;i<n;i++)
{
memset(l,false,sizeof(l));
memset(r,false,sizeof(r));
while(!dfs(i))
{
adjust();
memset(l,false,sizeof(l));
memset(r,false,sizeof(r));
}
}
for(int i=0;i<n;i++)
ans-=map[match[i]][i];
printf("Data Set %d, Best average difference: %.6f\n",tt,ans/n/2.0);
memset(match,-1,sizeof(match));
c=0;
search(0);
printf("\n");
}
return 0;
}