Codeforces 894E(Tarjan缩点+离线+DAG上最长路DP)

发表于 | 分类于 | | + s

Codeforces 894E
题意：给出$n$个点和$m$条有向边和出发点$fr$，求从$fr$出发可重复走的最大边权和，其中一条边如果走了一次边权就会减去当前走的次数，比如$w=56$，走过一次以后$w=56-1=55$，走过两次以后$w=56-1-2=55-2=53$，边权扣到0为止，0边权的边亦可以走。

考虑如果图中有一个强连通分量，那么这个强连通分量的所有边都可以走完(所有边权都为0)，所以考虑缩点。一个强连通分量的所有对答案贡献转为这个 强连通分量点 的点权。

如何计算边对答案的贡献? 可以二分解决，但是我这里运用了离线，先把所有边权存下来排序，然后一直进行$1+2+3+…$来决定每条边能过多少次及贡献。

然后新图就是一个DAG，在DAG上求个最长路即可，但是这幅图既有边权又有点权，所以不要忘记加上点权。

(btw: 人生第一题CFR div2E)

Codeforces Submission

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
LL n, m;//Input
struct data {
	LL x, y;
}ed[1000000 + 5];//原图中的边 
struct data2 {
	LL x, y, w;
}ed2[1000000 + 5];//新图中的边  
struct data3 {
	LL no, hw, w;
}wi2[1000000 + 5];//离线处理后的边权
bool cmp1(const data3 &a, const data3 &b) {
	return a.w < b.w;
}
bool cmp2(const data3 &a, const data3 &b) {
	return a.no < b.no;
}
vector<LL> G[1000000 + 5], R[1000000 + 5];//原图，新图 
LL totwi[1000000 + 5];//缩点后每个点的权 
LL vis[1000000 + 5], dfn[1000000 + 5], low[1000000 + 5], num[1000000 + 5], tb, en1, en2, totnum, fr, ans;
//访问数组，时间戳数组，最小追溯数组，原图每个点对应新图的强连通分量编号，时间戳计数，原图边计数，新图边计数，一共有多少个scc，输入起点，最后答案 
stack<LL> s;//Tarjan的stack，存节点
void ins1(LL x, LL y) {en1++, ed[en1] = (data){x, y}, G[x].push_back(en1);}//在原图插入一个新边 
void ins2(LL x, LL y, LL w) {en2++, ed2[en2] = (data2){x, y, w}, R[x].push_back(en2);}//在新图插入一个新边 
void tarjan(LL u) {//缩点 
	low[u] = dfn[u] = ++tb;
	vis[u] = -1, s.push(u);
	for (LL i = 0; i < (LL)G[u].size(); i++) {
		LL v = ed[G[u][i]].y;
		if (vis[v] == -1) low[u] = min(low[u], dfn[v]); 
		else if (vis[v] == 0) tarjan(v), low[u] = min(low[u], low[v]);
	}
	if (dfn[u] == low[u]) {
		LL e;
		totnum++;
		do {
			e = s.top(); s.pop();
			num[e] = totnum;
			vis[e] = 1;
		} while (e != u);
	}
}
void rebuild() {
	ms(vis, 0);
	for (LL i = 1; i <= m; i++) {
		if (num[ed[i].x] == num[ed[i].y]) totwi[num[ed[i].y]] += wi2[i].hw;
	}//计算强连通分量的边权和 
	for (LL u = 1; u <= n; u++) {
		for (LL i = 0; i < (LL)G[u].size(); i++) {
			LL v = ed[G[u][i]].y;
			if (num[v] == num[u] || vis[G[u][i]]) continue;
			vis[G[u][i]] = true;
			ins2(num[u], num[v], wi2[G[u][i]].w);//强连通分量之间的连边 
		}
	}
}
LL dfs(LL u) {
	if (vis[u] > 0) return vis[u];
	for (LL i = 0; i < (LL)R[u].size(); i++) {
		LL v = ed2[R[u][i]].y;
		vis[u] = max(vis[u], dfs(v) + ed2[R[u][i]].w + totwi[v]);//要加上点权 
	}
	ans = max(ans, vis[u]);
	return vis[u];
}
void clean() {//清除 
	ans = totnum = en1 = en2 = tb = 0;
	for (LL i = 0; i <= n; i++) {
		totwi[i] = num[i] = vis[i] = dfn[i] = low[i] = 0;
		G[i].clear(), R[i].clear();
	}
}
void solve() {
	clean();
	for (LL x, y, i = 1; i <= m; i++) {
		scanf("%I64d%I64d%I64d", &x, &y, &wi2[i].w);
		wi2[i].no = i, ins1(x, y);
	}
	scanf("%I64d", &fr);
	LL cnt = 1, i = 1, mdzz = 0, taki = 0;
	sort(wi2 + 1, wi2 + 1 + m, cmp1);
	while (i <= m) {
		mdzz += cnt;
		taki += mdzz;
		while (mdzz >= wi2[i].w && i <= m) {
			wi2[i].hw = wi2[i].w * cnt - (taki - mdzz), i++;
		}
		cnt++; 
	}//离线求每条边贡献 
	sort(wi2 + 1, wi2 + 1 + m, cmp2);
	for (LL i = 1; i <= n; i++) if (!vis[i]) tarjan(i);
	rebuild();
	ms(vis, 0), dfs(num[fr]);
	printf("%I64d\n", ans + totwi[num[fr]]);
}
int main() {
	scanf("%I64d%I64d", &n, &m), solve();
	return 0;
}

------ 本文结束 ------