洛谷---P3967 [TJOI2014]比對---最大二分帶權比對---KM算法

題目描述

有 NNN 個單身的男孩和 NNN 個單身女孩，男孩 iii 和女孩 jjj 在一起得到的幸福值為 Hi,jH_{i,j}Hi,j​。

一個比對即對這 NNN 個男孩女孩的安排：每個男孩恰好有一個女朋友，每個女孩恰好有一個男朋友。

一個比對的幸福值即這 NNN 對男女朋友的幸福值的和。

經典的問題是計算幸福值最大的比對，即完美比對。然而完美比對有時候并不唯一，你需要計算對于所有的完美比對，其交集是什麼。

輸入格式

輸入的第一行是一個正整數 NNN 。

接下來是一個 N×NN\times NN×N 大小的矩陣 HHH，Hi,jH_{i,j}Hi,j​ 表示男孩 iii 和女孩 jjj 在一起的幸福值。

輸出格式

第一行輸出完美比對的幸福值，接下來是若幹行，每一行是一對整數 iii 和 jjj，表示男孩 iii 和女孩 jjj 在所有完美比對的交集中，以 iii 的遞增順序輸出。

輸入輸出樣例

輸入 #1 複制

3
1 1 1
2 1 1
1 1 1      

輸出 #1 複制

4
2 1      

說明/提示

• 對于 30%30\%30% 的資料，N≤30N \leq 30N≤30；
• 對于 100%100\%100% 的資料，1≤N≤801\leq N \leq 801≤N≤80，0≤Hi,j≤5×1030\leq H_{i,j}\leq 5\times10^30≤Hi,j​≤5×103。

實作代碼

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int maxn = 105;
const int inf = 0x3f3f3f3f;

int	link[maxn][maxn];	
int ex_boy[maxn], ex_girl[maxn];	
bool vis_boy[maxn], vis_girl[maxn];		
int match[2][maxn];		
int slack[maxn];		
int n;

typedef pair<int, int> Mate;
Mate mate[maxn];
int cnt = 0;
bool cmp(Mate m1, Mate m2) { return m1.first < m2.first; }


bool dfs(int boy, int cnt) {
	vis_boy[boy] = true;
	for (int girl = 1; girl <= n; girl++) {
		if (vis_girl[girl]) continue;
		int dis = ex_boy[boy] + ex_girl[girl] - link[boy][girl];
		if (dis == 0) {
			vis_girl[girl] = true;
			if (!match[cnt][girl] || dfs(match[cnt][girl], cnt)) {
				match[cnt][girl] = boy;
				return true; // 比對成功
			}
		}
		else slack[girl] = min(slack[girl], dis);
	}
	return false;	// 比對失敗傳回失敗
}

int km(int cnt) {
	for (int i = 1; i <= n; i++) {
		match[cnt][i] = ex_girl[i] = 0;
		ex_boy[i] = link[i][1];
		for (int j = 2; j <= n; j++) ex_boy[i] = max(ex_boy[i], link[i][j]); 
	}
	for (int boy = 1; boy <= n; boy++) {
		for (int i = 1; i <= n; i++) slack[i] = inf;
		while (true) {
			memset(vis_boy, false, sizeof(vis_boy)); 
			memset(vis_girl, false, sizeof(vis_girl));
				
			if (dfs(boy, cnt)) break; // 如果比對成功就可以爬了
			// 沒比對成功就去降低期望值，因為初始化是最大期望，是以隻可以降

			int d = inf; // 最小減低的期望值
			for (int i = 1; i <= n; i++) if(!vis_girl[i]) d = min(slack[i], d);

			for (int i = 1; i <= n; i++) {
				// 修改比對過的兩者之間的期望值
				if (vis_boy[i]) ex_boy[i] -= d; 
				if (vis_girl[i]) ex_girl[i] += d;
				else slack[i] -= d;		//沒有比對的最小期望內插補點要下降
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) ans += link[match[cnt][i]][i]; 
	return ans;
}

int main() { 
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	while (cin >> n) {
		int max_ans = 0;
		for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> link[i][j];
		cout << (max_ans = km(0)) << endl;

		for (int i = 1; i <= n; i++) {
			int tmp = link[match[0][i]][i]; // 記錄第一次的比對期望
			link[match[0][i]][i] = 0;
			if (km(1) != max_ans) mate[cnt++] = Mate(match[0][i], i);
			link[match[0][i]][i] = tmp;
		}

		sort(mate, mate + cnt, cmp);
		for (int i = 0; i < cnt; i++) cout << mate[i].first << " " << mate[i].second << endl;
	}
	return 0;
}