CF1389G-Directing Edges
题目:
题目描述:
You are given an undirected connected graph consisting of $ n $ vertices and $ m $ edges. $ k $ vertices of this graph are special.
You have to direct each edge of this graph or leave it undirected. If you leave the $ i $ -th edge undirected, you pay $ w_i $ coins, and if you direct it, you don’t have to pay for it.
Let’s call a vertex saturated if it is reachable from each special vertex along the edges of the graph (if an edge is undirected, it can be traversed in both directions). After you direct the edges of the graph (possibly leaving some of them undirected), you receive $ c_i $ coins for each saturated vertex $ i $ . Thus, your total profit can be calculated as $ \sum \limits_{i \in S} c_i - \sum \limits_{j \in U} w_j $ , where $ S $ is the set of saturated vertices, and $ U $ is the set of edges you leave undirected.
For each vertex $ i $ , calculate the maximum possible profit you can get if you have to make the vertex $ i $ saturated.
输入格式:
The first line contains three integers $ n $ , $ m $ and $ k $ ( $ 2 \le n \le 3 \cdot 10^5 $ , $ n - 1 \le m \le \min(3 \cdot 10^5, \frac{n(n-1)}{2}) $ , $ 1 \le k \le n $ ).
The second line contains $ k $ pairwise distinct integers $ v_1 $ , $ v_2 $ , …, $ v_k $ ( $ 1 \le v_i \le n $ ) — the indices of the special vertices.
The third line contains $ n $ integers $ c_1 $ , $ c_2 $ , …, $ c_n $ ( $ 0 \le c_i \le 10^9 $ ).
The fourth line contains $ m $ integers $ w_1 $ , $ w_2 $ , …, $ w_m $ ( $ 0 \le w_i \le 10^9 $ ).
Then $ m $ lines follow, the $ i $ -th line contains two integers $ x_i $ and $ y_i $ ( $ 1 \le x_i, y_i \le n $ , $ x_i \ne y_i $ ) — the endpoints of the $ i $ -th edge.
There is at most one edge between each pair of vertices.
输出格式:
Print $ n $ integers, where the $ i $ -th integer is the maximum profit you can get if you have to make the vertex $ i $ saturated.
样例:
样例输入 1:
1
2
3
4
5
6
| 3 2 2
1 3
11 1 5
10 10
1 2
2 3
|
样例输出 1:
样例输入 2:
1
2
3
4
5
6
7
8
| 4 4 4
1 2 3 4
1 5 7 8
100 100 100 100
1 2
2 3
3 4
1 4
|
样例输出 2:
思路:
实现:
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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
| #include "ybwhead/ios.h"
const int N = 300043;
bool is_bridge[N];
int w[N];
int c[N];
int v[N];
vector<pair<int, int>> g[N];
vector<pair<int, int>> g2[N];
int comp[N];
long long sum[N];
long long dp[N];
int cnt[N];
int fup[N];
int tin[N];
int T = 0;
long long ans[N];
int v1[N], v2[N];
int n, m, k;
int dfs1(int x, int e)
{
tin[x] = T++;
fup[x] = tin[x];
for (auto p : g[x])
{
int y = p.first;
int i = p.second;
if (i == e)
continue;
if (tin[y] != -1)
fup[x] = min(fup[x], tin[y]);
else
{
fup[x] = min(fup[x], dfs1(y, i));
if (fup[y] > tin[x])
is_bridge[i] = true;
}
}
return fup[x];
}
void dfs2(int x, int cc)
{
if (comp[x] != -1)
return;
comp[x] = cc;
cnt[cc] += v[x];
sum[cc] += c[x];
for (auto y : g[x])
if (!is_bridge[y.second])
dfs2(y.first, cc);
}
void process_edge(int x, int y, int m, int weight)
{
long long add_dp = dp[y];
if (cnt[y] > 0 && cnt[y] < k)
add_dp = max(0ll, add_dp - weight);
cnt[x] += m * cnt[y];
dp[x] += m * add_dp;
}
void link(int x, int y, int weight)
{
process_edge(x, y, 1, weight);
}
void cut(int x, int y, int weight)
{
process_edge(x, y, -1, weight);
}
void dfs3(int x, int p)
{
dp[x] = sum[x];
for (auto e : g2[x])
{
int i = e.second;
int y = e.first;
if (y == p)
continue;
dfs3(y, x);
link(x, y, w[i]);
}
}
void dfs4(int x, int p)
{
ans[x] = dp[x];
for (auto e : g2[x])
{
int i = e.second;
int y = e.first;
if (y == p)
continue;
cut(x, y, w[i]);
link(y, x, w[i]);
dfs4(y, x);
cut(y, x, w[i]);
link(x, y, w[i]);
}
}
int main()
{
yin >> n >> m >> k;
for (int i = 0; i < k; i++)
{
int x;
yin >> x;
--x;
v[x] = 1;
}
for (int i = 0; i < n; i++)
yin >> c[i];
for (int i = 0; i < m; i++)
yin >> w[i];
for (int i = 0; i < m; i++)
{
scanf("%d %d", &v1[i], &v2[i]);
--v1[i];
--v2[i];
g[v1[i]].push_back(make_pair(v2[i], i));
g[v2[i]].push_back(make_pair(v1[i], i));
}
for (int i = 0; i < n; i++)
{
tin[i] = -1;
comp[i] = -1;
}
dfs1(0, -1);
int cc = 0;
for (int i = 0; i < n; i++)
if (comp[i] == -1)
dfs2(i, cc++);
for (int i = 0; i < m; i++)
if (is_bridge[i])
{
g2[comp[v1[i]]].push_back(make_pair(comp[v2[i]], i));
g2[comp[v2[i]]].push_back(make_pair(comp[v1[i]], i));
}
dfs3(0, 0);
dfs4(0, 0);
for (int i = 0; i < n; i++)
yout << ans[comp[i]] << " ";
puts("");
}
|