「Solution」二分图多重匹配 习题集

Posted on Edited on

题解集合

$\mathbb{Jamie's Contact Groups}$

$\mathcal{Link}$

link

$\mathcal{Sol}$

模板题，对于此类问题，解决方案可以是网络流。
对于匈牙利算法，有部分代码需要变动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool dfs(int u) {
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i];
		if (vis[v]) continue;
		vis[v] = 1;
		if (cnt[v] < limit[v]) { match[v][++cnt[v]] = u; return true; } //如果还可以继续匹配则继续
		for (int j = 1; j <= cnt[v]; j++) { // 否则就在已匹配的点中增广
			if (dfs(match[v][j])) {
				match[v][j] = u; return true;
			}
		}
	}
	return false;
}

$\mathcal{Code}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e3 + 5;

int n, m, l, r, mid, cnt[MAXN], match[MAXN][MAXN];
char tmp[15];
vector<int> G[MAXN];
bool vis[MAXN];

bool dfs(int u) {
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i];
		if (vis[v]) continue;
		vis[v] = 1;
		if (cnt[v] < mid) { match[v][++cnt[v]] = u; return true; }
		for (int j = 1; j <= cnt[v]; j++) {
			if (dfs(match[v][j])) {
				match[v][j] = u; return true;
			}
		}
	}
	return false;
}

bool check(int mid) {
	memset(cnt, 0, sizeof(cnt)); memset(match, 0, sizeof(match));
	for (int i = 1; i <= n; i++) {
		memset(vis, 0, sizeof(vis));
		if (!dfs(i)) return false;
	}
	return true;
}

int main() {

	// freopen("E.in", "r", stdin);
	// freopen("E.out", "w", stdout);

	while (scanf("%d %d", &n, &m) && (n + m)) {

		for (int i = 1, j; i <= n; i++) {
			G[i].clear();
			scanf("%s", tmp); char emsp;
			while (1) {
				scanf("%d%c", &j, &emsp);
				G[i].push_back(j); if (emsp == '\n') break;
			}
		}

		l = 1, r = n;

		while (l < r) {
			mid = (l + r) >> 1;
			if (check(mid)) r = mid;
			else l = mid + 1;
		}

		printf("%d\n", l);

	}

	return 0;
}

$\mathbb{Optimal Milking}$

$\mathcal{Link}$

link

$\mathcal{Sol}$

其实和网络流中奶牛躲雨棚一个思路。

首先$\mathcal{Floyd}$出来两两点之间的最短路。
然后二分答案。用匈牙利判匹配即可。

$\mathcal{Code}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = (200 << 1) + 5;
const int INF = 0x3f3f3f3f;

int n, m, l, r, mid, limit, dis[MAXN][MAXN], cnt[MAXN], match[MAXN][MAXN];
vector<int> G[MAXN];
bool vis[MAXN];

bool dfs(int u) {
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i];
		if (vis[v]) continue;
		vis[v] = 1;
		if (cnt[v] < limit) { match[v][++cnt[v]] = u; return true; }
		for (int j = 1; j <= cnt[v]; j++) {
			if (dfs(match[v][j])) {
				match[v][j] = u; return true;
			}
		}
	}
	return false;
}

bool check(int mid) {
	
	// printf("--%d--\n", mid);

	for (int i = n + 1; i <= n + m; i++) G[i].clear(); 
	memset(cnt, 0, sizeof(cnt)); memset(match, 0, sizeof(match));

	for (int i = 1; i <= n; i++) {
		for (int j = n + 1; j <= n + m; j++) if (dis[i][j] <= mid) {
			G[j].push_back(i);
			// printf("%d %d\n", j, i);
		}
	}

	for (int i = n + 1; i <= n + m; i++) {
		memset(vis, 0, sizeof(vis));
		if (!dfs(i)) return false;
	}

	return true;

}

int main() {

	// freopen("D:\\ChenJiage\\2021-12-23\\F.in", "r", stdin);
	// freopen("F.out", "w", stdout);

	scanf("%d %d %d", &n, &m, &limit);

	for (int i = 1; i <= n + m; i++) {
		for (int j = 1; j <= n + m; j++) {
			scanf("%d", &dis[i][j]);
			if (dis[i][j] == 0) dis[i][j] = INF;
		}
	}

	for (int k = 1; k <= n + m; k++)
		for (int i = 1; i <= n + m; i++)
			for (int j = 1; j <= n + m; j++) if (i != j)
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

	for (int i = 1; i <= n; i++)
		for (int j = n + 1; j <= n + m; j++)
			r = max(r, dis[i][j]);

	while (l < r) {
		mid = (l + r) >> 1;
		// printf("%d %d %d\n", l, mid, r);
		if (check(mid)) r = mid;
		else l = mid + 1;
	}	

	printf("%d\n", l);

	return 0;
}

$\mathbb{Steady Cow Assignment}$

$\mathcal{Link}$

link

$\mathcal{Sol}$

哈哈哈哈，这个阴间输入，哈哈哈。

输入挂了，一直$\mathtt{WA \ Test \ 6}$，总共就 $\mathtt{7}$个点。
什么鬼东西。。。

然后值域很小，直接枚举区间就能过。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e3 + 5;
const int MAXM = 25;
const int INF = 0x3f3f3f3f;

int n, m, ans, limit[MAXM], p[MAXN][MAXM], match[MAXM][MAXN], cnt[MAXM];
vector<int> G[MAXN];
bool vis[MAXM];

bool dfs(int u) {
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i];
		if (vis[v]) continue;
		vis[v] = 1;
		if (cnt[v] < limit[v]) { match[v][++cnt[v]] = u; return true; }
		for (int j = 1; j <= cnt[v]; j++) {
			if (dfs(match[v][j])) {
				match[v][j] = u; return true;
			}
		}
	}
	return false;
}

bool check(int l, int r) {

	memset(cnt, 0, sizeof(cnt));
	memset(match, 0, sizeof(match));
	memset(vis, 0, sizeof(vis));
	for (int i = 1; i <= n; i++) G[i].clear();

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) if (p[i][j] >= l && p[i][j] <= r) {
			G[i].push_back(j);
		}
	}

	for (int i = 1; i <= n; i++) {
		memset(vis, 0, sizeof(vis));
		if (!dfs(i)) return false;
	}

	return true;

}

int main() {

	// freopen("G.in", "r", stdin);
	// freopen("G.out", "w", stdout);

	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++)
		for (int j = 1, x; j <= m; j++)
			scanf("%d", &x), p[i][x] = j;

	for (int i = 1; i <= m; i++) scanf("%d", &limit[i]);

	ans = INF;
	for (int l = 1; l <= m; l++) {
		for (int r = l; r <= m; r++) {

			if (check(l, r)) ans = min(ans, r - l + 1);

		}
	}

	printf("%d\n", ans);

	return 0;
}
The End
「Ô mon âme, n'aspire pas à la vie immortelle, mais épuise le champ du possible.」