题解 P3967 【[TJOI2014]匹配】
雨季
2018-03-04 21:11:48
# 题解
题意很明确
### 第一问
$\quad \ \ $求带权二分图的最佳完美匹配，然而并不会写带权匹配╮(╯▽╰)╭，于是写了最大费用最大流。
建图：$\ \ \ \ $超级源 $\ \ \ \ \ \to \ \ \ \ \ $ 男生$(i)$ $\qquad\ $容量为1，费用为0
$\ \ \ \ $ $\qquad\ $男生$(i)$ $ \ \ \ \ \to\ $ 女生$(j+n)\ $容量为1，费用为幸福值
$\quad\ \ \ \ $女生$(j+n)$$$\ \ \ \to\ \ \ \ \ $超级汇$\qquad\ \ \ \ $容量为1，费用为0
### 第二问
$\quad \ \ $求出所有完美匹配中都有的边
$\quad \ \ $通过第一问，我们知道了一个完美匹配的方案，以及完美匹配下的最大幸福值。
$\quad \ \ $那么我们可以枚举这个完美匹配中的每一条边，将它删掉，再次跑完美匹配，如果这次的最大费用比没有删掉它之前的答案小了，那么说明这条边一定在完美匹配中
**注：如果写费用流的话，删边时记的将这条边对应的反向边一起删掉，不然的话你大概会死循环。。。**
# 代码
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define N 500
int n,S,T;
bool in[N][N];
bool check[N*N];
inline int read() {
int tmp=0,w=1;
char ch=0;
while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
while(isdigit(ch)) tmp=(tmp<<1)+(tmp<<3)+ch-'0',ch=getchar();
return tmp*w;
}
struct node {
int u,v,c,f,nex;
}e[N*N],ee[N*N];
int tot=1,h[N],use[N];
void add(int u,int v,int c,int f) {
e[++tot].u=u,e[tot].v=v,e[tot].c=c,e[tot].f= f,e[tot].nex=h[u],h[u]=tot;
e[++tot].u=v,e[tot].v=u,e[tot].c=0,e[tot].f=-f,e[tot].nex=h[v],h[v]=tot;
}
int dis[N];
bool vis[N];
bool donot[N*N];
deque<int>q;
bool spfa() {
for(int i=S;i<=T;++i) dis[i]=-1e9,vis[i]=0;
q.push_back(T);
dis[T]=0;
int x,xx;
while(!q.empty()) {
x=q.front();
q.pop_front();
vis[x]=0;
for(int i=h[x];i;i=e[i].nex) {
xx=e[i].v;
if(donot[i]) continue;
if(e[i^1].c&&dis[xx]<dis[x]-e[i].f) {
dis[xx]=dis[x]-e[i].f;
if(!vis[xx]) {
vis[xx]=1;
if(q.empty()||dis[xx]<dis[q.front()]) q.push_back(xx);
else q.push_front(xx);
}
}
}
}
return dis[S]>-1e9;
}
bool mark[N];
int dfs(int x,int want) {
mark[x]=1;
if(x==T||!want) return want;
int f=0,get=0,xx=0;
for(int i=use[x];i;i=e[i].nex) {
if(donot[i]) continue;
xx=e[i].v;
if(e[i].c&&!mark[xx]&&dis[xx]==dis[x]-e[i].f) {
f=dfs(xx,min(want,e[i].c));
if(!f) continue;
e[i].c-=f;
e[i^1].c+=f;
get+=f;
want-=f;
use[x]=i;
if(!want) break;
}
}
return get;
}
int mfmc() {
int res=0;
while(spfa()) {
mark[T]=1;
while(mark[T]) {
for(int i=S;i<=T;++i) use[i]=h[i],mark[i]=0;
res+=dis[S]*dfs(S,1e9);
}
}
return res;
}
int main()
{
scanf("%d",&n);
S=0,T=n+n+1;
int x;
for(int i=1;i<=n;++i) {
for(int j=1;j<=n;++j) {
x=read();
add(i,j+n,1,x);
}
}
int cut=tot;
for(int i=1;i<=n;++i) add(S,i,1,0),add(i+n,T,1,0);
memcpy(ee,e,sizeof(e));
int ans=mfmc();
for(int i=2;i<=cut;i+=2) if(!e[i].c) check[i]=1;
printf("%d\n",ans);
for(int i=2;i<=cut;i+=2) {
if(check[i]) {
donot[i]=1,donot[i^1]=1;
memcpy(e,ee,sizeof(ee));
x=mfmc();
if(x<ans) in[e[i].u][e[i].v]=1;
donot[i]=0,donot[i^1]=0;
}
}
for(int i=1;i<=n;++i) {
for(int j=1;j<=n;++j) {
if(in[i][j+n]) printf("%d %d\n",i,j);
}
}
return 0;
}
```