HDU 2853 & 剩余系+KM模板

题意：

　　给你一张二分图，给一个原匹配，求原匹配改动最少的边数使其边权和最大。

SOL：

　　我觉得我的智商还是去搞搞文化课吧。。这种题给我独立做我大概只能在暴力优化上下功夫。。

　　这题的处理方法让我想到了剩余系。。貌似就是它。。

　　我们将每条边的边权扩大n+1倍——是不是有点雾，同时将原匹配边的边权再加1.

　　非常玄学！这样做有什么道理呢？它保证了最优匹配在这样更改后仍是最优的！我们假设次优解比最优解只小1，在乘上n+1后差距被放大到n+1，即使次优解全由原匹配边组成，加上n仍小于最优解，那么我们就一定能求出最优解。同时我们注意到每一条边的边权均为n+1的倍数，而原匹配边的边权为n+1的倍数加1，那么我们就能很方便地求出当前解中有多少原匹配边。

　　如果原图有多个最优解，那么我们能肯定拥有原匹配边最多的解在乘上n+1后边权最大——毕竟人家加了1嘛。

　　很巧妙的剩余系转化与运用啊。。数学渣确实已经没救了。

/*==========================================================================

# Last modified: 2016-02-19 13:00

# Filename: hdu2853.cpp

# Description:

==========================================================================*/

#define me AcrossTheSky

#include <cstdio>

#include <cmath>

#include <ctime>

#include <string>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <vector>

#define lowbit(x) (x)&(-x)

#define INF 1070000000

#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)

#define FORP(i,a,b) for(int i=(a);i<=(b);i++)

#define FORM(i,a,b) for(int i=(a);i>=(b);i--)

#define ls(a,b) (((a)+(b)) << 1)

#define rs(a,b) (((a)+(b)) >> 1)

#define maxn 100

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

/*==================split line==================*/

int n,m;

int slack[maxn],lx[maxn],ly[maxn],w[maxn][maxn],link[maxn];

bool S[maxn],T[maxn];

int Ans;

bool match(int i){

	S[i]=true;

	FORP(j,1,m)

	if (!T[j]){

		int tmp=lx[i]+ly[j]-w[i][j];

		if (tmp==0){

			T[j]=true;

			if (!link[j] || match(link[j])){

				link[j]=i;

				return true;

			}

		}

		else slack[j]=min(slack[j],tmp);

	}

	return false;

}

void updata(){

	int a=INF;

	FORP(i,1,m) if (!T[i]) a=min(a,slack[i]);

	FORP(i,1,n) if (S[i]) lx[i]-=a;

	FORP(i,1,m)

		if (T[i]) ly[i]+=a;

			else slack[i]-=a;

}

void KM(){

	memset(lx,0,sizeof(lx));

	memset(link,0,sizeof(link));

	memset(ly,0,sizeof(ly));

	FORP(i,1,n)

		FORP(j,1,m) lx[i]=max(lx[i],w[i][j]);

	FORP(i,1,n){

		memset(slack,0x7f,sizeof(slack));

		while (true){

			memset(S,false,sizeof(S));

			memset(T,false,sizeof(T));

			if (match(i)) break;

			else updata();

		}

	}

	int ans=0;

	FORP(i,1,m) if (link[i]) ans+=w[link[i]][i];

	printf("%d %d\n",n-ans%(n+1),ans/(n+1)-Ans/(n+1));

}

int main(){

	freopen("a.in","r",stdin);

	while (scanf("%d%d",&n,&m)!=EOF){

		Ans=0;

		FORP(i,1,n)

			FORP(j,1,m) {

				int x;

				scanf("%d",&x);

				w[i][j]=x*(n+1);

			}

		FORP(i,1,n) {int x; scanf("%d",&x); Ans+=w[i][x]; w[i][x]++;}

		KM();

	}

}