https://codeforces.com/contest/1368

E. Ski Accidents

 

题意：给定一个有向图，限定只从小节点连向大节点，且每个节点出度不超过 2。要求删掉不超过 47n\frac{4}{7}n 个点，使得图上不存在长度大于 1 的路径。

贪心

遍历每条路径，当走到第3个点时，就把第3个点删掉。

证明也是实现方式：

设 V0V_0 为没有入度或者入度全为被删点的点，即删完后每条路径的起点。

V1V_1 为每条路径的第2个点，即存在 V0V_0 指向它的点。

V1V_1 为每条路径的第3个点，也就是要删掉的点，即存在 V1V_1 指向它的点。

由于每点出度最大为2，所以 V1≥12V2V_1\ge \frac{1}{2}V_2，V0≥12V1≥14V2V_0\ge \frac{1}{2}V_1\ge \frac{1}{4}V_2。

由定义容易发现，每点都恰属于一类，所以 n=V0+V1+V2n=V_0+V_1+V_2。

所以 n≥74V2n\ge \frac{7}{4}V_2，即 V2≤47nV_2\le \frac{4}{7}n。

本题的数字大小也就是拓扑序，所以直接按顺序遍历即可。

这题我一直纠结在删第2个点，觉得更赚，但其实反而不好。

要说怎么能想到，可能还是4/7这个数字比较特殊，或者先猜出贪心删第3个点，然后证明吧。

如果把本题的出度限制改成入度，就不能这样做了，因为点数的限制就没有了。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 2e5 + 10;
int T;
vector<int>G[N], ans;
int co[N];
int main() {
	scanf("%d", &T);
	while (T--) {
		int n, m;
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i++)G[i].clear();
		ans.clear();
		fill(co, co + n + 1, 0);
		for (int i = 0; i < m; i++) {
			int u, v;
			scanf("%d%d", &u, &v);
			G[u].push_back(v);
		}
		for (int i = 1; i <= n; i++) {
			if (co[i] == 2)ans.push_back(i);
			else {
				for (int v : G[i]) {
					co[v] = max(co[v], co[i] + 1);
				}
			}
		}
		printf("%d\n", (int)ans.size());
		for (int u : ans)printf("%d ", u);
		puts("");
	}
	return 0;
}