http://poj.org/problem?id=2400
KM算法http://philoscience.iteye.com/blog/1754498
题意:每个雇主对雇员有个满意度 雇员对雇主有个满意度 求最匹配的雇员与雇主
最小权匹配 这个给出的数据矩阵貌似是反着的 建图的时候反一下就好了
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stdlib.h>
#define N 110
#define INF 0x3f3f3f
using namespace std;
int w[N][N],n,x[N],y[N],lx[N],ly[N],link[N],sum,o[N],vis[N],num;
bool match(int u)
{
x[u] = ;
for(int i = ; i <= n ; i++)
if(lx[u]+ly[i]==w[u][i]&&!y[i])
{
y[i] = ;
if(!link[i]||match(link[i]))
{
link[i] = u;
return true;
}
}
return false;
}
double km()
{
int i,j,g;
for(i = ; i <= n ; i++)
link[i] = lx[i] = ly[i]=;
for(i = ; i <= n ; i++)
{
for(;;)
{
for(j = ;j <= n ; j++)
x[j] = y[j] = ;
if(match(i)) break;
int d = INF;
for(j = ; j <= n ; j++)
{
if(x[j])
for(g = ; g <= n ; g++)
if(!y[g])
d = min(d,lx[j]+ly[g]-w[j][g]);
}
for(j = ; j <= n ; j++)
{
if(x[j]) lx[j]-=d;
if(y[j]) ly[j]+=d;
}
}
}
sum=;
for(i = ; i <= n ; i++)
sum-=(lx[i]+ly[i]);
return 1.0*sum/(*n);
}
void dfs(int u,int ss)
{
int i;
if(ss>sum) return ;
if(u==n+)
{
printf("Best Pairing %d\n",++num);
for(i = ;i <= n ; i++)
printf("Supervisor %d with Employee %d\n",i,o[i]);
return ;
}
for(i = ; i <= n ; i++)
{
if(!vis[i])
{
vis[i] = ;
o[u] = i;
dfs(u+,ss-w[u][i]);
vis[i] = ;
}
}
}
int main()
{
int i,j,kk=,cas,a;
scanf("%d",&cas);
while(cas--)
{
kk++;num=;
scanf("%d",&n);
memset(w,,sizeof(w));
memset(vis,,sizeof(vis));
for(i = ; i <= n ; i++)
for(j = ; j <= n ; j++)
{
scanf("%d",&a);
w[a][i] -= j;
}
for(i = ; i <= n ; i++)
for(j = ; j <= n ; j++)
{
scanf("%d",&a);
w[i][a]-=j;
}
double s = km();
printf("Data Set %d, Best average difference: %.6f\n",kk,s-);
dfs(,);
puts("");
}
return ;
}