首页 题解 洛谷

题目传送门

# 题意分析：

看到这个题面，很容易想到是求二分图最大权完美匹配。

建图的话用邻接矩阵或者链式前向星都很容易，以及求最大权也很简单。
但难就难在第二个操作。

第二个操作的内容： 经典的问题是计算幸福值最大的匹配，即完美匹配。然而完美匹配有时候并不唯一，你需要计算对于所有的完美匹配，其交集是什么。

运用 KM 或者 Dinic 都很容易求得完美匹配的幸福数，但是题目中可能出现多种完美匹配，用题目中的样例来举例。

3
1 1 1
2 1 1
1 1 1
  1. 1→22→13→11 \rightarrow 2 \quad 2 \rightarrow 1 \quad 3 \rightarrow 1
  2. 1→32→13→11 \rightarrow 3 \quad 2 \rightarrow 1 \quad 3 \rightarrow 1
  3. 1→22→13→21 \rightarrow 2 \quad 2 \rightarrow 1 \quad 3 \rightarrow 2
  4. 1→32→13→21 \rightarrow 3 \quad 2 \rightarrow 1 \quad 3 \rightarrow 2

对于样例，会有以上四种完美匹配，那么题目中的交集是什么呢？

就是第二个男同学选择第一个女同学，因为只有这样才能是幸福之最大的匹配。

也就是样例输出的：

最大幸福值： 4
交集：       2 1

所以这个题目中所谓的交集，就是为了构成最大幸福值所必须选择的一些搭配 。

所以我们可以明显的发现一个性质：如果这些搭配中有一个会不选，那么最大幸福值就会变小。

但是还有一个方面需要大家注意，举个例子：

3
1 1 1
2 2 1
1 1 1

那么这个时候的交集是什么呢？

你会发现它 没有交集 ，因为它没有必须选的，那你可以有疑问，那个第二个男生与第一个女生或者第二个女生所产生的幸福值一样啊，那不得两个选一个，这不肯定有交集了吗？

不要忘了在数学上集合的定义是：设 AA ， BB 是两个集合，由所有属于集合 AA 且属于集合 BB 的元素所组成的集合，叫做集合 AA 与集合 BB 的交集 。

所以得是构成每个最大幸福值所必选的，每个最大幸福值都需要这一些搭配的才是交集。

所以运用所必须的搭配一定会影响最大幸福值这一性质，我们就可以解决题目啦。

至此，题目理解结束。

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#include<queue>
#define int long long
using namespace std;
struct node{
	int x,y;
}p[1010];
bool cmp(node a,node b){
	return a.x<b.x;
}
const int INF=0x3f3f3f3f3f;
const int N=550;
int n,m,match[N],pri[N];// 数组定义看文末
bool vis2[N];
long long fav[N][N],val1[N],val2[N],sla[N];
void bfs(int k){// 正常的 BFS 求二分图最大权完美匹配啦
	int x,y=0,z=0;
	memset(pri,0,sizeof(pri));
	memset(sla,INF,sizeof(sla));
 	match[0]=k;
	do{
		int d=INF;
		x=match[y];
		vis2[y]=true;
		for(int i=1;i<=n;i++){
			if(vis2[i]){
				continue;
			}
			if(sla[i]>val1[x]+val2[i]-fav[x][i]){
				sla[i]=val1[x]+val2[i]-fav[x][i];
				pri[i]=y;
			}
			if(sla[i]<d){
				d=sla[i];
				z=i;
			}
		}
		for(int i=0;i<=n;i++){
			if(vis2[i]){
				val1[match[i]]-=d;val2[i]+=d;
			}else{
				sla[i]-=d;
			}
		}
		y=z;
	}while(match[y]);
	while(y){
		match[y]=match[pri[y]];
		y=pri[y];
	}
}
int KM(){
	memset(match,0,sizeof(match));
	memset(val1,0,sizeof(val1));
	memset(val2,0,sizeof(val2));
	for(int i=1;i<=n;i++){
		memset(vis2,false,sizeof(vis2));
		bfs(i);
	}
	int res=0;
	for(int i=1;i<=n;i++){
		res+=fav[match[i]][i];
	}
	return res;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>fav[i][j];
		}
	}
	int ans=KM();
	cout<<ans<<endl;
	for(int i=1;i<=n;i++){
		p[i].x=match[i],p[i].y=i;
	}
	sort(p+1,p+n+1,cmp);
	for(int i =1;i<=n;i++){
		int k=fav[p[i].x][p[i].y];
		fav[p[i].x][p[i].y]=-INF;// 断开某一条边
		if(KM()<ans){// 重新跑一次 KM，判断最大值是否有变化
			cout<<p[i].x<<" "<<p[i].y<<endl;
		} 
		fav[p[i].x][p[i].y]=k;
	}
}
/*
设置最大期望值
利用匈牙利算法找增广路
找到增广路，匹配成功，退出
找不到，最小程度降低男生期望，提升女生期望
继续回到 (2) 开始重复
*/
/*val1 [N]/val2 [N] 分别记录 U 集与 V 集点的点权（匹配期望值）
vis1 [N]/vis2 [N] 分别记录每次寻找增广路过程中 U 集与 V 集点的访问情况
match [N] 记录最终 V 集内点匹配到的在 U 集内点的编号
slack [N] 记录匹配过程中，U 集内任意点能够选择 V 集内任意点作为匹配对象所需要降低 val（期望值）的最小值
*/
感谢阅读！