自动搬运

查看原文

来自洛谷，原作者为

	雨季 **

搬运于2025-08-24 21:55:02，当前版本为作者最后更新于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 \ \$那么我们可以枚举这个完美匹配中的每一条边，将它删掉，再次跑完美匹配，如果这次的最大费用比没有删掉它之前的答案小了，那么说明这条边一定在完美匹配中
注：如果写费用流的话，删边时记的将这条边对应的反向边一起删掉，不然的话你大概会死循环。。。

代码

#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;
}