大连建设工程设计院有限公司网站/seo外链怎么做能看到效果

题目链接：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=1;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=1;i<=m;i++) //nyif(!T[i]&&slack[i]<a) a=slack[i];for(int i=1;i<=n;i++)  //nxif(S[i]) LX[i]-=a;for(int i=1;i<=m;i++) //ny
    {if(T[i]) RX[i]+=a;else slack[i]-=a;}
}
void KM()
{memset(link,0,sizeof(link));memset(RX,0,sizeof(RX));for(int i=1;i<=n;i++) //nxfor(int j=1;j<=m;j++) //nyLX[i]=max(LX[i],W[i][j]);for(int i=1;i<=n;i++) //nx
    {for(int j=1;j<=m;j++) //nyslack[j]=inf;while(1){memset(S,0,sizeof(S));memset(T,0,sizeof(T));if(dfs(i)) break;else update();}}int res=0,change=0;for(int i=1;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,0,sizeof(W));memset(Hash,0,sizeof(Hash));old=0;K=n+1;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&W[i][j]);W[i][j]*=K;}for(int i=1;i<=n;i++){scanf("%d",&tmp);old+=(W[i][tmp]/K);Hash[tmp]=i;W[i][tmp]++;}KM();memset(slack,0,sizeof(slack));memset(LX,0,sizeof(LX));}return 0;
}