自动搬运

查看原文

来自洛谷，原作者为

	Usada_Pekora 兎田ぺこら/大傻Peko_Official/AFO

搬运于2025-08-24 21:43:52，当前版本为作者最后更新于2022-08-18 15:55:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题外话：写了 SPJ 过了两个月终于有管理员回了（虽然没被采纳但是对了），这道题总算能交了。

题意：有 $n$ 个人与 $m$ 个小组，对于每个小组，给出小组的大小 $k$ 和组内人员。若第 $i$ 个人参加了 $j$ 个小组，这 $j$ 个小组的大小分别为 $k_{p_1},k_{p_2}...k_{p_j}$，则他可以匹配这 $j$ 个小组中的 $\lceil\sum^j_{l=1}\frac{1}{k_{p_l}}\rceil$ 个。问使每个小组都被匹配的方案。

匹配！不难想出二分图匹配这个做法：用每个人去匹配组，然后检验最大匹配数，最后输出方案。然而本题一个点可以同时匹配好多点，直接这么做显然是不可以的，不过可以考虑拆点做。

当一个点可以向 $f$ 个点连出边，我们可以将其拆成 $f$ 个点，每个新点在图中的连边关系与原点一样。如此一来，这 $f$ 个点每个点匹配一个点，就等同于这个点匹配了 $f$ 个点。

拆完点后，我们在新图上跑二分图匹配即可，需要注意处理拆完的点与原先点的关系，用右部的小组点来匹配会少一些细节问题。

代码如下（复杂度会比寻常的二分图匹配大一些，因为我们拆点增加了点数）：

#include <bits/stdc++.h>
using namespace std;
const int N = 1005, M = 105;
int n, m, tot;
double c[N];
int matx[N], maty[N], id[N * M];
bool vis[N], g[M][N];
inline bool dfs(int u) {//匈牙利算法
	for(int i = 1; i <= tot; i++) {
		if(!g[u][id[i]] || vis[i]) continue;
		vis[i] = 1;
		if(!maty[i] || dfs(maty[i])) {
			matx[u] = i;
			maty[i] = u;
			return 1;
		}
	}
	return 0;
}
int main() {
	cin >> n >> m;
	for(int i = 1, x; i <= m; i++) {
		cin >> x;
		for(int j = 1, y; j <= x; j++) {
			cin >> y;
			c[y] += 1.0 / x;
			g[i][y] = 1;
		}
	}
	for(int i = 1; i <= n; i++) {
		int f = ceil(c[i]);
		while(f--) id[++tot] = i;//将 i 拆成 f 个点
	}
	for(int i = 1; i <= m; i++) {
		memset(vis, 0, sizeof vis);
		if(!dfs(i)) {
			cout << -1 << '\n';
			return 0;
		}
	}
	for(int i = 1; i <= m; i++)
		cout << id[matx[i]] << '\n';
	return 0;
}

本题还存在一种不需要拆点，且理论复杂度更优的做法，复杂度上界约为 $O((n+m)\sqrt{n+m})$。

将其转化为多源汇最大流模型，每个人最多匹配 $f$ 个小组，则从源点向他连流量为 $f$ 的边；一个小组只能被一个人匹配一次，则每个人向他所在的小组连一条流量为 $1$ 的边；一个小组仅能被匹配一次，则向汇点连流量为 $1$ 的边。

然后直接 Dinic 跑一次，因为是二分图，所以复杂度为 $O(E\sqrt V)$，一共有 $n+m$ 个点，第一个步骤连了 $2n$ 条边，第二个步骤最多连 $38m$ 条边，第三个步骤连了 $2m$ 条边，约去常数后大概是上面的复杂度。

对于方案输出，我们判断一条从人流向小组的正向边流量是否为 $0$，为 $0$ 则明这个人匹配了这个小组。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 1005, M = 105, E = 19 * M + N + M;
double c[N];
int dep[N], n, m, s, t, fir[N + M], nxt[E << 1], to[E << 1], flow[E << 1], cnt = 1, mat[M];
inline void add(int u, int v, int f) {
	to[++cnt] = v;
	flow[cnt] = f;
	nxt[cnt] = fir[u];
	fir[u] = cnt;
}
inline bool bfs() {
	memset(dep, 0, sizeof dep);
	dep[s] = 1;
	queue<int> q;
	q.push(s);
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(int i = fir[u]; i; i = nxt[i]) {
			if(flow[i] && !dep[to[i]]) {
				q.push(to[i]);
				dep[to[i]] = dep[u] + 1;
			}
		}
	}
	return dep[t] > 0;
}
inline int min(int x, int y) {
	return x < y ? x : y;
}
inline int dfs(int u, int in) {
	if(u == t) return in;
	int out = 0, res;
	for(int i = fir[u]; i && in; i = nxt[i]) {
		if(dep[to[i]] == dep[u] + 1 && flow[i]) {
			res = dfs(to[i], min(in, flow[i]));
			flow[i] -= res, flow[i ^ 1] += res, in -= res, out += res;
		}
	}
	if(out == 0) dep[u] = 0;
	return out;
}
inline int dinic() {
	int res = 0;
	while(bfs()) res += dfs(s, 1e9);
	return res;
}
int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	s = 0, t = n + m + 1;
	for(int i = 1, x; i <= m; i++) {
		cin >> x;
		for(int j = 1, y; j <= x; j++) {
			cin >> y;
			c[y] += 1.0 / x;
			add(y, i + n, 1);
			add(i + n, y, 0);
		}
	}
	for(int i = 1; i <= n; i++) {
		int f = ceil(c[i]);
		add(s, i, f);
		add(i, s, 0);
	}
	for(int i = 1; i <= m; i++) {
		add(i + n, t, 1);
		add(t, i + n, 0);
	}
	int maxf = dinic();
	if(maxf == m) {
		for(int i = 1; i <= n; i++) {
			for(int j = fir[i]; j; j = nxt[j]) 
				if(to[j] != s && flow[j] == 0) mat[to[j] - n] = i;
		}
		for(int i = 1; i <= m; i++) printf("%d\n", mat[i]);
	} else puts("-1");
	return 0;
}