Fork me on GitHub

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

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;
}

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