mydcwfy's Blog

LOJ3702 「联合省选 2022」学术社区

Posted on
Symbols count in article: 4.9k Reading time ≈ 11 mins.

题意：有 $n$ 个人发了 $m$ 条消息，消息分为“xxx 楼下”“xxx 楼上”和学术消息。你需要合理安排这 $m$ 条消息的顺序，使得符合实际条件的楼上、楼下型消息尽量多，需要给出构造。保证每个人至少发了一条学术消息。$n\leq m\leq 77777$，$\sum m\leq 2.5\times 10 ^ 5$。

本题特殊性质有较强的提示性，我们根据特殊性质来解题。

  1. 特殊性质 A：不会存在楼上型消息。
  2. 特殊性质 B：保证存在一种顺序使得每一条楼上、楼下型消息都符合实际。
  3. 特殊性质 C：保证不同时存在“A 说在 B 楼下”和“B 说在 A 楼上”。

特殊性质 ABC

考虑我们如果有一条 “A 在 B 楼下”的消息，我们 从 B 向 A 连一条边，那么现在一条完整的链就是从一条学术消息开始经过楼下型消息转移，最后在任意点停下。如果我们建立虚拟节点 T，任意一条学术消息我们都从 T 向这个点连边，这样的话就是从 T 开始到任意点结束的路径。

由于保证每条楼下型消息都符合实际，说明每个点的入度一定不小于出度，否则有些出边一定不能从 T 开始。对于多出来的，我们可以考虑链覆盖相关的算法欧拉回路，那么我们把一个点的（入度减去出度）条边从这个点引向 T，那么我们就从 T 开始求出欧拉回路即可。建的多出来的边不考虑就好了。

特殊性质 AC

现在去掉了保证符合实际的条件该怎么办？

现在相当于问题在于每个点的入度可能小于出度，这个时候我们将 T 向这个点连（出度减去入度）条边即可。注意每个点如果入度小于出度，那么答案应该减去（出度减去入度）。换言之，答案应该加上 $\min(\text{indeg} (x), \text{outdeg} (x))$。

特殊性质 BC

现在开始有楼上型消息了，我们怎么建图？

首先一个问题是楼上和楼下型消息其实不同点很多的，主要就在于其实两种的发出人并不相同。

我们可以考虑这样建图：建立 $G_1, G_2$，每个点在 $G_1, G_2$ 中都对应一个点，如果形如“A 在 B 楼上”就在 $G_1$ 中从 A 向 B 连边，形如“A 在 B 楼下”就在 $G_2$ 中从 B 向 A 连边，如果是学术消息就从 $G_1$ 对应点连向 $G_2$。

容易发现在特殊性质 C 范围下，一条完整链条形如任意楼上型消息链 - 学术消息 - 任意楼下型消息链。这个在建图中对应着一条从 $G_1$ 中点连到 $G_2$ 中点的一条链。那么既然每条都符合实际，那么说明 $G_1$ 中出度不小于入度，$G_2$ 中入度不小于出度。类似于上面的建图，我们从虚拟节点 $T$ 向 $G_1$ 中的点连边，从 $G_2$ 中的点向 T 连边，这样的话我们寻找欧拉回路，减去没有实际存在的边，就可以得到构造方案了。

特殊性质 C

现在没有了 $G_1$ 出度不小于入度，$G_2$ 入度不小于出度，这个该怎么办呢？

注意到如果我们直接按照 特殊性质 AC 的计算的话，答案一定有一个下界 $\sum \min(\text{indeg}(x), \text{outdeg}(x))$。但是注意到我们有些并没有用到，我们可不可以合适的调整一下呢？

调整的方法显然是我们把一条原来是一条楼上或者楼下型消息改为学术消息。以一条楼上型消息为例，“A 在 B 楼上”的消息原来是 $G_1$ 中 A 向 B 连边，现在是 $G_1$ 中 A 向 $G_2$ 中 A 连边。原来 B 的出度过大，减少 1 不会影响答案，而 $G_2$ 中 A 的出度过小的话，增加 1 就会使得答案 +1。那么这样更改的话就是有效的。

我们可以通过一个网络流模型来刻画：如果 $G_1$ 中出度小于入度，就从 S 向该点连容量为 $\text{indeg}(x) - \text{outdeg}(x)$ 的边。向上面一样刻画两两之间的边，$G_2$ 中如果入度小于出度，就向 T 连容量为 $\text{outdeg}(x) - \text{indeg}(x)$。这样跑出来的网络流就是答案的增加量。

然后考虑怎么构造。其实是好构造的，我们对于每条边，找到其在网络流中对应的边，如果流过了，说明这条消息变成了学术消息，否则没有。向上面那样建图，存在出入度差异就用虚拟节点平衡，从虚拟节点开始欧拉回路就可以找到一个合法的构造了。

无特殊性质

这个相较于特殊性质 C 来说多了一个中间环节：可能直接是楼上型消息链 - 楼下型消息链。注意到这两条消息放在一起是好的，所以我们直接放在一起。比如是”A 在 B 楼上“和”B 在 A 楼下“两个消息，我们直接从 $G_1$ 中的 A 向 $G_2$ 中的 B 连边即可。同样参与出入度的统计，注意这样直接答案 +2，因为原来这个是一条学术消息，我们没有计算其答案，现在就需要直接 +2。这个等价于二分图匹配，使用 dinic 可以做到复杂度 $O(m\sqrt m)$，可以通过。

实现

写起来细节还行，主要是没有特殊性质的话，找到对应的楼上楼下型消息比较麻烦（没有保证任意两条消息不同），然后就是没有特殊性质的话，一条欧拉回路上的边可能实际代表两条边，所以需要压缩一下。然后对于 $\text{indeg}$ 和 $\text{outdeg}$ 的处理可能细节稍多，可以参考一下代码。

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
86
87
88
89
void dfs(int x)
{
	for (int &i = h[x], v, j; ~i;) {
		v = e[i], j = i;
		i = ne[i];
		dfs(v);
		seq[++ etot] = w[j];
	}
}

void work()
{
	std::cin >> n >> m;
	std::map<std::string, int> gid;
	std::map<std::pair<int, int>, int> alledg;
	clear();
	std::string s1, s2, s3;
	for (int i = 1; i <= n; ++ i) std::cin >> s1, gid[s1] = i;
	for (int i = 1; i <= m; ++ i)
	{
		std::cin >> s1 >> s2 >> s3;
		if ((s3 == "louxia" || s3 == "loushang") && gid.count(s2))
			mg[++ tot] = {gid[s1], gid[s2], s3 == "louxia", i};
		else xs[gid[s1]].push_back(i);
	}
	
	for (int i = 1; i <= tot; ++ i)
		if (!mg[i].typ) alledg[{mg[i].i1, mg[i].i2}] ++;
	int tmptot = 0, res = 0;
	for (int i = tot; i; -- i) {
		if (!mg[i].typ) continue;
		int &x = alledg[{mg[i].i2, mg[i].i1}];
		if (!x) nw[++ tmptot] = mg[i];
		else x --, res += 2;
	}
	std::map<std::pair<int, int>, std::vector<int>> predg;
	for (int i = 1; i <= tot; ++ i)
		if (mg[i].typ) predg[{mg[i].i2, mg[i].i1}].push_back(i);
	for (int i = 1; i <= tot; ++ i) {
		if (mg[i].typ) continue;
		auto &v = predg[{mg[i].i1, mg[i].i2}];
		if (v.empty()) nw[++ tmptot] = mg[i];
		else {
			add(mg[i].i1, mg[i].i2 + n, (LL) mg[i].id * m + mg[v.back()].id);
			outdeg[mg[i].i1] ++, indeg[mg[i].i2 + n] ++, v.pop_back();
		}
	}
	for (int i = 1; i <= tmptot; ++ i) mg[i] = nw[i];
	tot = tmptot;
	
	for (int i = 1; i <= tot; ++ i)
		if (mg[i].typ) outdeg[mg[i].i2 + n] ++, indeg[mg[i].i1 + n] ++;
		else outdeg[mg[i].i1] ++, indeg[mg[i].i2] ++;
	for (int i = 1; i <= n; ++ i)
		outdeg[i] += xs[i].size(), indeg[i + n] += xs[i].size();
	G.S = 2 * n + 1, G.T = 2 * n + 2;
	for (int i = 1; i <= n; ++ i)
		if (indeg[i] > outdeg[i]) G.add(G.S, i, indeg[i] - outdeg[i]);
	for (int i = n + 1; i <= 2 * n; ++ i)
		if (indeg[i] < outdeg[i]) G.add(i, G.T, outdeg[i] - indeg[i]);
	for (int i = 1; i <= 2 * n; ++ i) res += std::min(indeg[i], outdeg[i]);
	for (int i = 1; i <= tot; ++ i)
		if (mg[i].typ) eid[i] = G.idx, G.add(mg[i].i1, mg[i].i2 + n, 1);
		else eid[i] = G.idx, G.add(mg[i].i2, mg[i].i1 + n, 1);
	G.dinic();
	for (int i = 1; i <= 2 * n; ++ i) indeg[i] = outdeg[i] = 0;
	for (int i = 1; i <= tot; ++ i)
		if (!G.w[eid[i]]) res ++, add(mg[i].i1, mg[i].i1 + n, mg[i].id);
		else if (mg[i].typ) add(mg[i].i2 + n, mg[i].i1 + n, mg[i].id);
		else add(mg[i].i1, mg[i].i2, mg[i].id);
	for (int i = 1; i <= n; ++ i)
		for (int id : xs[i]) add(i, i + n, id);
	for (int x = 1; x <= 2 * n; ++ x)
		for (int i = h[x]; ~i; i = ne[i]) outdeg[x] ++, indeg[e[i]] ++;
	for (int i = 1; i <= 2 * n; ++ i)
		if (indeg[i] < outdeg[i]) {
			for (int j = 1; j <= outdeg[i] - indeg[i]; ++ j) add(2 * n + 1, i, 0);
		} else {
			for (int j = 1; j <= indeg[i] - outdeg[i]; ++ j) add(i, 2 * n + 1, 0);
		}
	dfs(2 * n + 1);
	std::cout << res << '\n';
	for (int i = etot; i; -- i) {
		if (!seq[i]) continue;
		if (seq[i] <= m) std::cout << seq[i] << ' ';
		else std::cout << (seq[i] - 1) / m << ' ' << (seq[i] - 1) % m + 1 << ' ';
	}
	std::cout << '\n';
}