题解 P4014 【分配问题】
Khassar
2017-12-27 08:56:43
非常裸的二分图最佳完美匹配。
我们把人放一边，工作放一边，效率就是边权，然后求一个**权值和**最大和（或）最小的完美匹配。
至于二分图最佳完美匹配的求法，我在这里只简单说一下，具体的可以自找资料学习。
首先，介绍一个重要的定理：
我们定义**顶标**：
lx[i],ly[j],i∈左边，j∈右边，并且对于任意w[i][j],都有lx[i]+ly[j]>=w[i][j]；
我们再从原图中抽出lx[i]+ly[j]=w[i][j]的边建立一个**相等子图**，如果相等子图有**完美匹配**（就是无边权，全匹配的那个），那么这个完美匹配就是原图的**最佳完美匹配**。
这个定理的证明也十分简单，这里我就不证明了，有兴趣的可以自行百度。
有了这个定理我们就可以用KM(匈牙利算法)求解此题了。
具体的方法就是，不断的修改顶标让它有一个合适的值，使得相等子图有完美匹配。实现起来就是先开心地设一个顶标初值（一般是ly=0,lx=max(w[i][j])），然后开始KM，如果找到了一条增广路，就找到了吧；如果没有，那它一定是尝试访问了一些左边的点（比如q个）我们把它们加入**S**,然后访问了q-1个右边的点,我们把它们加入**T**（S,T是两个集合）。
然后把lx[i],i∈S都减去一个**松弛量a**，ly[j],j∈T，都加上一个a，这样就会有一些不在T中的点和在S中的点之间的边能够进入相等子图，同时已经在相等子图里的边不出去，继续进行KM直到匹配了这个点为止。
至于找a的方法，为了保证进来的边是能进来的之中最大的，同时又有边进来，
a=min{lx[i]+ly[j]-w[i][j]|i∈S，j∉T}，这个过程就n^2暴力枚举就好了，因此整个算法时间复杂度为n^4，当然还有一个n^3的优化方法，不过n^4就能0ms秒杀此题，所以这里就不用了。
这里讲的并不是很深，有些概念没有涉及，建议大家最好还是上网查些资料好好学一下。
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\~我是分割线~////////////////////
上面是求的最大值，怎么求最小值呢？
把边权整体取负啊。
最终答案嘛：根据相等子图的定义就是顶标和了。
最后贴代码，再不济只能看代码了。
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<vector>
#include<ctime>
#define ll long long
#define R register
#define IL inline
#define Rf(a,b,c) for(R int (a)=(b);(a)<=(c);++(a))
#define Tf(a,b,c) for(R int (a)=(b);(a)>=(c);--(a))
#define MP make_pair
#define PA pair<int,int>
#define MES(a,b) memset((a),(b),sizeof((a)))
#define MEC(a,b) memset((a),(b),sizeof((b)))
#define D double
using namespace std;
const int N=505;
int n,m,lx[N],ly[N],link[N],w[N][N];
bool S[N],T[N];
IL int read() {
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x*=10;x+=(ch-'0');ch=getchar();}
return x*f;
}
IL void write(int x) {
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
bool dfs(int x) {//这就是一般的二分图匹配
S[x]=true;//把左边的点都加入S
Rf(i,1,n)
if(lx[x]+ly[i]==w[x][i]&&!T[i]) {//判断这条边是否在相等子图里，不要再建图了
T[i]=true;//右边的点加入T
if(!link[i]||dfs(link[i])) {
link[i]=x;
return true;
}
}
return false;
}
IL void update() {//n^2暴力找a，并修改
R int a=1<<30;
Rf(i,1,n) if(S[i])
Rf(j,1,n) if(!T[j])
a=min(a,lx[i]+ly[j]-w[i][j]);
Rf(i,1,n) {
if(S[i]) lx[i]-=a;
if(T[i]) ly[i]+=a;
}
}
IL void KM() {
Rf(i,1,n) {
link[i]=lx[i]=ly[i]=0;
Rf(j,1,n) lx[i]=max(lx[i],w[i][j]);//顶标初值
}
Rf(i,1,n) while(true) {
Rf(j,1,n) S[j]=T[j]=false;//记得每次都要清空
if(dfs(i)) break;//找到增广路了
else update();//没找到就得松弛了
}
}
signed main()
{
n=read();
Rf(i,1,n) Rf(j,1,n) w[i][j]=read();
KM();
int sum1=0,sum2=0;
Rf(i,1,n) sum1+=lx[i]+ly[i];//最后的顶标和就是最终答案了
Rf(i,1,n) Rf(j,1,n) w[i][j]*=-1;//整体取负跑最小
KM();
Rf(i,1,n) sum2+=lx[i]+ly[i];
write(-sum2);//记得要把答案再取负回来啊
putchar('\n');write(sum1);
return 0;
}
```