「JOISC 2016 Day 3」电报

发表于
https://loj.ac/problem/2737

题目链接

「JOISC 2016 Day 3」电报

做法

考虑形成环的条件是将若干环和基环內向树拆成若干条链，然后依次拼接成环（特判给出的图已经是完整一个环的情况）。
枚举每一个连通块。若该联通块是一个环，则断开代价最小的边；否则进行拓扑排序。
先考虑不在环上的部分。假如一个点他有若干入度，显然只有其中一个入度能够保留，贪心地保留代价最大的入度。如此化简后得到一个环（环上每个点可能有一条不在环上的链）。
然后在环上DP。由于环一定要断开，令 $ f[i][0/1][0/1] $ 表示环上第 $ i $ 个点，环有/没有被断开过，这个点选择的是断开环上的边还是链上的边。
时间复杂度 $ O(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
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 100010;
int n, to[N], c[N], In[N], tmp[N], val[N]; ll ans, f[2][2][N];
vector<int> e[N], a, cir, hv[N];
bool vis[N], used[N];
queue<int> q;

bool check() {
	int u = 1; rep(i, 1, n) { if(vis[u]) return 0; vis[u] = 1, u = to[u]; }
	if(u == 1) return 1; return 0;
}
void Find(int x) {
	vis[x] = 1, a.pb(x); if(!vis[to[x]]) Find(to[x]);
	for(auto v : e[x]) if(!vis[v]) Find(v);
}
void solve(int x) {
	a.clear(), cir.clear(), Find(x); int lst = a[0];
	for(auto v : a) tmp[v] = In[v];
	for(; !q.empty(); q.pop()); for(auto v : a) if(!In[v]) q.push(v);
	if(q.empty()) {
		int mn = 2e9; for(auto v : a) mn = min(mn, c[v]); ans += mn; return ;
	}
	for(int u; !q.empty();) {
		u = q.front(), q.pop(), used[u] = 1;
		if(hv[u].size() > 1) {
			sort(hv[u].begin(), hv[u].end());
			rep(i, 0, (int)hv[u].size() - 2) ans += hv[u][i];
		}
		if(In[to[u]] > 1) hv[to[u]].pb(c[u]);
		lst = to[u], --tmp[to[u]]; if(!tmp[to[u]]) q.push(to[u]);
	}
	cir.pb(lst); for(int u = to[lst]; u != lst; u = to[u]) cir.pb(u);
	for(auto v : cir) {
		sort(hv[v].begin(), hv[v].end());
		rep(i, 0, (int)(hv[v].size() - 2)) ans += hv[v][i];
		if(hv[v].size()) val[v] = hv[v].back();
	}
	f[0][0][0] = c[cir.back()], f[1][1][0] = val[cir[0]];
	f[1][0][0] = f[0][1][0] = (ll)1e14;
	rep(i, 1, (int)(cir.size() - 1)) {
		f[0][0][i] = min(f[1][1][i - 1], min(f[0][1][i - 1], f[0][0][i - 1])) + c[cir[i - 1]];
		f[0][1][i] = min(f[0][1][i - 1], f[0][0][i - 1]) + val[cir[i]];
		f[1][0][i] = (ll)1e14;
		f[1][1][i] = f[1][1][i - 1] + val[cir[i]];
	}
	ans += min(f[0][0][(int)(cir.size() - 1)], f[0][1][(int)(cir.size() - 1)]);
}
int main() {
	scanf("%d", &n);
	rep(i, 1, n) scanf("%d%d", &to[i], &c[i]), e[to[i]].pb(i), ++In[to[i]];
	if(check()) { puts("0"); return 0; }
	memset(vis, 0, sizeof(vis));
	rep(i, 1, n) if(!vis[i]) solve(i);
	printf("%lld\n", ans);
	return 0;
}