[AGC045E] Fragile Balls

建议不要阅读这篇题解

太难描述了..我写的很不清楚,但是太花时间了我暂时懒得改了。建议去看其他题解。

吐槽

巨大的分类讨论,样例还巨弱,每次 WA 都让人怀疑是算法假了。。。

做法

考虑一个 (不一定是简单图的) \(n\) 个点的有向图 \(G\),把点编号为 \(1\ldots n\),这个图初始没有边。对于一个初始在盒子 \(A_i\),目标是放到盒子 \(B_i\),可以操作至多 \(C_i\) 次的球 \(i\),在点 \(A_i\) 到点 \(B_i\) 之间添加一条边权为 \(C_i\) 的有向边。

根据题目中每个箱子最终都有球的条件,\(G\) 中每个点的入度都不为 \(0\)

题目中的一次操作,相当于选取一条边权为正数且起点的出度大于 \(1\) 的边,修改这条边的起点,然后把边权减小 \(1\)。要求用最少次数的操作使得每条边都是一个自环。

后文中一个有向图的弱连通块指的是,把有向边看成无向边后的一个连通块。后文中,说一个弱连通块是一个简单环,是指这个弱连通块仅由一个简单环构成 (不包含除此以外的任何边,或是重边、自环)。

特别考虑所有点出度都小于等于 \(1\) 的情况。因为入度之和等于出度之和,所以每个点的出度一定都恰好为 \(1\),此时 \(G\) 的每个弱连通块都是一个简单环。如果每个连通块都是自环,那么答案为 \(0\),否则无解。下面我们不讨论这种情况。

我们来考虑一个新的问题:

问题 1 假设初始时 \(G\) 中所有点都为白色。在任何时刻,如果某个某个点的出度大于等于 \(2\),那么它所在的初始时的弱连通块中所有点都会被染黑。每次你可以选取一条起点为黑点的有向边,修改它的起点。问最少多少步可以让所有边变为自环。

显然这个问题的答案小于等于原问题的答案,因为原问题可以进行的操作这个问题上都可以进行。

我们来考虑这个问题的最优方案。假设某个合法操作序列中包含一次操作,这次操作把某条边的起点改为了这次操作之前就已经被染黑的某个点,且这不是对这条边的最后一次操作,那么我们可以从操作序列中删去这个操作,操作序列依然合法。所以最优的方案是不会包含这样的操作的。

先来考虑不存在一个弱连通块点数边数都为 \(1\) 的情况,问题可以转化成如下形式:

  1. 你有一个金币数,初始为 \(0\)
  2. 一条边有三种状态:未被你拥有,被你拥有但未被使用,被你拥有且已被使用。初始时所有边都未被你拥有。
  3. 游戏开始时,你会拥有所有开始时就被染黑的弱连通块中的边。
  4. 每次操作,你可以进行做以下两件事中的一件
    1. 如果你的金币数为正,你可以消耗 \(1\) 金币,选择一个未被染黑的弱连通块将其染黑,然后这个弱连通块中所有边将被你拥有。这次操作的代价为 \(0\)
    2. 你可以选择一条你已经拥有但未被使用的边,假设这条边可以被操作 \(C_i\) 次,如果这条边是一个自环,这次操作的代价为 \(1\),否则这次操作的代价为 \(0\)。接下来这条边的状态会被变为已被使用,你的金币数会增加 \(C_i-1\)
  5. 你的目的是染黑所有点,最小化所有操作的代价之和。

假设 问题 1 的答案为 \(a\),这个游戏的答案为 \(b\),初始时有 \(c\) 个未被染黑的弱连通块,\(d\) 个非自环边,那么 \(a = b + d + c\)

如果我们解决了这个问题,那么如果存在点数边数都为 \(1\) 的弱连通块,我们可以枚举有多少个这样的弱连通块最终要被染黑,我们一定会选取包含的边的 \(C_i\) 最大的若干个点数边数都为 \(1\) 的弱连通块。然后用上述问题的算法解决。所以现在我们只需得到能在不存在只有一个点一条边的弱连通块的前提下求出上述游戏答案的算法。

分两种情况讨论:

Case 1 你进行过至少一次操作 \(1\)。那么在你进行第一次操作 \(1\) 之前,你必须获得至少 \(1\) 金币。对于一种合法操作方案,对应一个初始时未被染黑的弱连通块的收益为,这个弱连通块中所有被使用了的边的 \(C_i - 1\) 之和再减去 \(1\)。那么,如果我们把初始时未被染黑的连通块按收益从大到小排序,依次对每个连通块进行操作 \(1\),然后再使用这个操作方案中使用了的边。这样得到的操作方案一定也合法,而且代价不变。所以我们只需考虑这样的操作方案。注意到,如果只确定了使用哪些边,存在一种这样的操作方案的充要条件是,所有初始时被染黑的连通块中被使用的边的 \(C_i-1\) 之和大于 \(0\),且所有被使用过的边的 \(C_i-1\) 之和大于等于初始时未被染黑的弱连通块数。这样问题就被转化为了只有代价为 \(0\) 的物品和代价为 \(1\) 的物品的背包问题。排个序搞个前缀和就能解决。

多次询问可以用二分优化。

Case 2 你没有进行过操作 \(1\)。那么游戏开始时,所有未被染黑的连通块中的边都必须是自环。此时所有操作代价和最小值为 \(0\)

这样我们就解决了 问题 1。之前已经说过 问题 1 的答案小于等于原问题的答案,现在我们来证明 问题 1 的答案大于等于原问题的答案。

假设我们知道了 问题 1 的一个需要操作 \(k\) 步的方案。现在我们回到图 \(G\) 中考虑问题。

定义 1\(G\) 的一个子图是好的当且仅当它不是一个大小大于 \(1\) 的有向环。

引理 1 对于一个好的弱连通块,可以用这个弱连通块中非自环边数次操作把这个弱连通块中所有边变为自环。

证明 假设对于所有非自环边数小于 \(k\) 的好的弱连通块上述结论都成立。现在我们来证明对非自环边数等于 \(k\) 的好的弱连通块,上述结论也成立。根据图 \(G\) 的定义,每个点的入度都不为 \(0\)。如果一个弱连通块中有自环,那么这个弱连通块一定是好的。我们找到任意一个入度为 \(0\) 的 SCC。

Case 1. 这个 SCC 大小大于 \(1\)

假设这个 SCC 对应的子图是好的,那么一定有一个点出度大于 \(1\) (否则就是一个基环树和内向树构成的森林,又是 SCC 所以一定是一个不好的连通块)。找到这个点的一条出边,把这条边改成自环。根据 SCC 的定义,这条出边指向的点出发可以走到这个 SCC 所有点。也就是说这个弱连通块的连通性没有发生改变,非自环边数恰好减小了 \(1\)。根据归纳假设,结论成立。

假设这个 SCC 对应的子图不是好的,即它是一个环。因为这个弱连通块是好的,它至少有一条出边,从而有一个点在整个弱连通块中出度大于 \(1\)。选取这个点在环上的出边,把它变成自环,分析同上面的情况。

Case 2. 这个 SCC 大小为 \(1\)

由于入度不为 \(0\),所以这个 SCC 肯定由一些自环组成,选取这个 SCC 的一条出边,变成自环。如果此时这个弱连通块变成了两个弱连通块,那么两个弱连通块都包含自环,所以它们都是好的,根据归纳假设可以用总共 \(k-1\) 次操作把它们中的所有边变成自环。否则根据归纳假设也可以用 \(k-1\) 次操作把所有边变成自环。所以结论成立。

\(G\) 的每一个弱连通块看作一个点。建一个有向图。如果 问题 1 的方案中,某次操作修改了 \(G\) 的某个弱连通块 \(A\) 中的一条边,使得弱连通块 \(B\) 第一次被染黑,就在 \(A\)\(B\) 连一条有向边。这样得到的图是若干个有向 (外向) 树构成的森林。

对于弱连通块 \(u\),设 \(u\) 子树中所有弱连通块中的点构成的集合为 \(S\)。假设操作 \(dfs(u)\) 可以在当前 \(S\) 的导出子图与初始时相同,且弱连通块 \(u\) 中的点当前在某个好的弱连通块中的前提下,只操作初始在 \(S\) 导出子图中的边,把初始在 \(S\) 导出子图中的边全部变成自环。

我们递归地定义 \(dfs(u)\):设 \(u\) 对应的弱连通块为 \(S\),假设 \(S\) 中有 \(c\) 条非自环边,根据 引理 1 可以用 \(c\) 次操作把 \(S\) 中的边变成自环。(如果有 \(S\) 外的点连边到 \(S\) 内,可以通过在 \(S\) 中加自环转化为 引理 1 中的情况)考虑一个恰好需要 \(c\) 次的操作方案。我们在这个操作方案的基础上修改,在把一条非自环边变成自环之前,先检查是否有 \(u\) 的儿子 \(v\) 对应的弱连通块,在 问题 1 的方案中被对这条边的操作染黑 (且 \(v\) 没有被访问过),如果有,设 问题 1 的方案中把这条边的起点改成了弱连通块 \(v\) 中的点 \(x\)。把这条边的起点改为点 \(x\)。然后递归 \(dfs(v)\),由于每个点都有入度,回溯时一定有点 \(x\) 上的自环。所以这时点 \(x\) 的出度大于 \(1\),可以继续修改这条边的起点。再检查是否有 \(v\) 的其他儿子需要这样操作,如果有,继续修改然后 \(dfs\)。否则把这条边改为自环。同样地,在每个原本就是自环的边第一次出度大于等于 \(2\) 时,我们也执行类似的操作。可以发现每个自环都一定会被执行到一次。

上述构造可以得到一个操作次数不大于 问题 1 的答案的原问题的方案。

所以只需输出 问题 1 的答案即可。

时间复杂度 \(\mathcal O(n \log n)\)

代码

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 100010;

int n, m, ans = 0x3f3f3f3f;

int tot, cnt;
int eu[maxn], ev[maxn], ec[maxn], vis[maxn], deg[maxn];
int tag[maxn], cid[maxn];

vector<int> to[maxn], fr[maxn];
vector<int> vv[maxn], ve[maxn];

int ex[maxn];

void dfs(int u) {
vis[u] = 1;
if (deg[u] > 1) ex[tot] = 1;
vv[tot].push_back(u);
for (int i = 0; i < to[u].size(); i++) {
int v = ev[to[u][i]], e = to[u][i];
ve[tot].push_back(e); cid[e] = tot;
if (!vis[v]) {
dfs(v);
}
}
for (int i = 0; i < fr[u].size(); i++) {
int v = eu[fr[u][i]];
if (!vis[v]) {
dfs(v);
}
}
}

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v, c; scanf("%d%d%d", &u, &v, &c);
cnt += (u != v);
eu[i] = u, ev[i] = v, ec[i] = c;
to[u].push_back(i), fr[v].push_back(i);
++ deg[u];
}
int flag1 = 0;
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
++ tot;
dfs(i);
if (vv[tot].size() > 1 && !ex[tot]) {
++ flag1;
}
if (ex[tot]) {
for (int j = 0; j < ve[tot].size(); j++) {
tag[ve[tot][j]] = 1;
}
}
}
}
if (!flag1) {
ans = cnt;
} else {
ll sum = 0;
int flag2 = 0;
for (int i = 1; i <= m; i++) {
if (ec[i] == 1) continue;
if (eu[i] != ev[i] && tag[i]) {
flag2 = 1;
}
if (eu[i] != ev[i]) sum += ec[i] - 1;
}
vector<int> v0, v1;
for (int i = 1; i <= m; i++) {
if (ec[i] == 1 || eu[i] != ev[i]) continue;
if (!tag[i]) v0.push_back(ec[i] - 1);
else v1.push_back(ec[i] - 1);
}
sort(v0.begin(), v0.end(), greater<int>()); sort(v1.begin(), v1.end(), greater<int>());
vector<ll> s0(v0.size(), 0), s1(v1.size(), 0);
for (int i = 0; i < v0.size(); i++) {
if (!i) s0[i] = v0[i];
else s0[i] = s0[i-1] + v0[i];
}
for (int i = 0; i < v1.size(); i++) {
if (!i) s1[i] = v1[i];
else s1[i] = s1[i-1] + v1[i];
}
if (flag2) {
for (int i = 0; i <= v0.size(); i++) {
int k = flag1 + i;
ll need = k - sum;
if (i > 0) need -= s0[i-1];
if (need <= 0) {
ans = min(ans, k + cnt + i);
} else {
int p = int (lower_bound(s1.begin(), s1.end(), need) - s1.begin());
if (p < s1.size()) {
ans = min(ans, k + cnt + i + (p + 1));
}
}
}
} else {
for (int i = 0; i <= v0.size(); i++) {
int k = flag1 + i;
ll need = k - sum;
if (i > 0) need -= s0[i-1];
int p = int (lower_bound(s1.begin(), s1.end(), need) - s1.begin());
if (p < s1.size()) {
ans = min(ans, k + cnt + i + (p + 1));
}
}
}
}
if (ans >= 0x3f3f3f3f) puts("-1");
else printf("%d\n", ans);
return 0;
}