题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2853
题目大意：二分图匹配费用流。①最大匹配②最小原配变动
解题思路：
如果去掉第二个要求，那么就是裸KM。
然而加上第二个要求，那么就需要一种新的建图方式。
建图
对于输入矩阵，每一条边，cost扩大K倍($K=n+1$)
对于原配，每一条边cost在扩大K倍基础上+1
KM
统计cost时，直接把cost整除K，然后累加。
并且Hash一下原配边的变动情况。
扩大K倍的作用
准确来说，K倍是为了+1而存在的。由于要优先考虑原配边，所以cost要大些。
但是，加大的cost又要使得最后好统计真实的cost。所以选择扩大K倍，然后整除K，这样，+1会被直接舍掉。
K=n+1是防止n=1的情况被卡姿势。
代码
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
using namespace std;
#define maxn 55
int n,m,Hash[maxn],tmp,old,K;
int link[maxn],LX[maxn],RX[maxn],W[maxn][maxn],slack[maxn],e[maxn][maxn];
bool S[maxn],T[maxn];
const int inf=0x3f3f3f3f;
bool dfs(int u)
{
S[u]=true;
for(int v=;v<=m;v++)
{
if(T[v]) continue;
int t=LX[u]+RX[v]-W[u][v];
if(!t)
{
T[v]=true;
if(!link[v]||dfs(link[v]))
{
link[v]=u;
return true;
}
}
else if(t<slack[v]) slack[v]=t;
}
return false;
}
void update()
{
int a=inf;
for(int i=;i<=m;i++) //ny
if(!T[i]&&slack[i]<a) a=slack[i];
for(int i=;i<=n;i++) //nx
if(S[i]) LX[i]-=a;
for(int i=;i<=m;i++) //ny
{
if(T[i]) RX[i]+=a;
else slack[i]-=a;
}
}
void KM()
{
memset(link,,sizeof(link));
memset(RX,,sizeof(RX));
for(int i=;i<=n;i++) //nx
for(int j=;j<=m;j++) //ny
LX[i]=max(LX[i],W[i][j]);
for(int i=;i<=n;i++) //nx
{
for(int j=;j<=m;j++) //ny
slack[j]=inf;
while()
{
memset(S,,sizeof(S));
memset(T,,sizeof(T));
if(dfs(i)) break;
else update();
}
}
int res=,change=;
for(int i=;i<=m;i++) //ny
{
if(link[i])
{
res+=(W[link[i]][i]/K);
if(Hash[i]!=link[i]) change++;
}
}
printf("%d %d\n",change,res-old);
}
int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(W,,sizeof(W));
memset(Hash,,sizeof(Hash));
old=;K=n+;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%d",&W[i][j]);
W[i][j]*=K;
}
for(int i=;i<=n;i++)
{
scanf("%d",&tmp);
old+=(W[i][tmp]/K);
Hash[tmp]=i;
W[i][tmp]++;
}
KM();
memset(slack,,sizeof(slack));
memset(LX,,sizeof(LX));
}
return ;
}