题解 P3967 【[TJOI2014]匹配】
Khassar
2018-03-07 15:25:05
我觉得费用流的那篇题解已经把题意说清楚了，所以我就特来贡献一下二分图最佳完美匹配的KM写法。
具体理论一些的东西你们可以去看我在$P4014$写的题解，里面说的比较多这里就不在写了。
要特别注意的是虽然我用的是$n^3$优化过的KM（我那篇题解里用的是$n^4$的，我会在代码里用注释简单说一下$n^3$优化，其实就是加了个松弛量slack），但还是在加上$n^2$枚举删边后华丽丽地TLE了3个点。
所以需要在枚举时判一下这条边有没有可能成为答案（具体看代码吧）
```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) memcpy((a),(b),sizeof((b)))
#define D double
using namespace std;
const int N=105;
int n,m,lx[N],ly[N],link[N],w[N][N],sl[N],sum,Ans,Link[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;
Rf(i,1,n)
if(lx[x]+ly[i]==w[x][i]) {
if(!T[i]) {
T[i]=true;
if(!link[i]||dfs(link[i])) {
link[i]=x;
return true;
}
}
}
else {//用不能进入相等子图的边更新一下松弛量sl
sl[i]=min(sl[i],lx[x]+ly[i]-w[x][i]);
}
return false;
}
IL void update() {
R int a=1e9;
Rf(j,1,n) if(!T[j]) //在松弛量中找，而不是再n^2枚举，优化在此
a=min(a,sl[j]);
Rf(i,1,n) {
if(S[i]) lx[i]-=a;
if(T[i]) ly[i]+=a;
sl[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;sl[j]=1e9;
}
if(dfs(i)) break;
else update();
}
}
signed main()
{
n=read();
Rf(i,1,n) Rf(j,1,n) w[i][j]=read();
KM();
Rf(i,1,n) sum+=lx[i]+ly[i];
write(sum);putchar('\n');
Ans=sum;MEC(Link,link);//先记录一个最佳完美匹配
Rf(k,1,n) Rf(j,1,n) {//枚举删边
if(w[k][j]<w[Link[j]][j]) continue;
//如果这条边比j在一个最佳完美匹配中匹配的边的边权要小，那么这条边一定不会在任意一个最佳完美匹配中，就没必要尝试删它。
R int tmp=w[k][j];
w[k][j]=-1e7;
sum=0;
KM();
Rf(i,1,n) sum+=lx[i]+ly[i];
w[k][j]=tmp;
if(sum!=Ans) {
printf("%d %d\n",k,j);
}
}
return 0;
}
```
啦啦啦，KM跑得飞快