CF757F-Team Rocket Rises Again
题目:
题目描述:
It’s the turn of the year, so Bash wants to send presents to his friends. There are $ n $ cities in the Himalayan region and they are connected by $ m $ bidirectional roads. Bash is living in city $ s $ . Bash has exactly one friend in each of the other cities. Since Bash wants to surprise his friends, he decides to send a Pikachu to each of them. Since there may be some cities which are not reachable from Bash’s city, he only sends a Pikachu to those friends who live in a city reachable from his own city. He also wants to send it to them as soon as possible.
He finds out the minimum time for each of his Pikachus to reach its destination city. Since he is a perfectionist, he informs all his friends with the time their gift will reach them. A Pikachu travels at a speed of $ 1 $ meters per second. His friends were excited to hear this and would be unhappy if their presents got delayed. Unfortunately Team Rocket is on the loose and they came to know of Bash’s plan. They want to maximize the number of friends who are unhappy with Bash.
They do this by destroying exactly one of the other $ n-1 $ cities. This implies that the friend residing in that city dies, so he is unhappy as well.
Note that if a city is destroyed, all the roads directly connected to the city are also destroyed and the Pikachu may be forced to take a longer alternate route.
Please also note that only friends that are waiting for a gift count as unhappy, even if they die.
Since Bash is already a legend, can you help Team Rocket this time and find out the maximum number of Bash’s friends who can be made unhappy by destroying exactly one city.
输入格式:
The first line contains three space separated integers $ n $ , $ m $ and $ s $ ( $ 2<=n<=2·10^{5} $ , 
, $ 1<=s<=n $ ) — the number of cities and the number of roads in the Himalayan region and the city Bash lives in.
Each of the next $ m $ lines contain three space-separated integers $ u $ , $ v $ and $ w $ ( $ 1<=u,v<=n $ , $ u≠v $ , $ 1<=w<=10^{9} $ ) denoting that there exists a road between city $ u $ and city $ v $ of length $ w $ meters.
It is guaranteed that no road connects a city to itself and there are no two roads that connect the same pair of cities.
输出格式:
Print a single integer, the answer to the problem.
样例:
样例输入1:
1
2
3
4
5
| 4 4 3
1 2 1
2 3 1
2 4 1
3 1 1
|
样例输出1:
样例输入2:
1
2
3
4
5
6
7
8
9
10
11
12
| 7 11 2
1 2 5
1 3 5
2 4 2
2 5 2
3 6 3
3 7 3
4 6 2
3 4 2
6 7 3
4 5 7
4 7 7
|
样例输出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
| // Problem: CF757F Team Rocket Rises Again
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF757F
// Memory Limit: 500 MB
// Time Limit: 2500 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include "ybwhead/ios.h"
typedef long long ll;
const ll N = 200005, INF = 0x3f3f3f3f3f3f3f3f;
//支配树
ll d[N], sz[N], f[N][20];
ll dis[N];
bool vst[N];
vector<ll> es[N], tree[N];
void add(ll u, ll v)
{
tree[u].push_back(v);
d[v] = d[u] + 1, f[v][0] = u;
for (ll i = 1; i < 20; i++)
f[v][i] = f[f[v][i - 1]][i - 1];
}
ll LCA(ll x, ll y)
{
if (d[x] < d[y])
swap(x, y);
for (ll i = 19; i >= 0; i--)
if (d[f[x][i]] >= d[y])
x = f[x][i];
if (x == y)
return x;
for (ll i = 19; i >= 0; i--)
if (f[x][i] != f[y][i])
x = f[x][i], y = f[y][i];
return f[x][0];
}
void build(ll u)
{
if (vst[u])
return;
vst[u] = 1;
ll fa = 0;
for (auto x : es[u])
build(x);
for (auto x : es[u])
if (!fa)
fa = x;
else
fa = LCA(fa, x);
add(fa, u);
}
void dfs(ll u)
{
sz[u] = (dis[u] != INF);
for (auto v : tree[u])
if (v != f[u][0])
dfs(v), sz[u] += sz[v];
}
//建图
ll n, m, s;
struct edge
{
ll t, w;
edge(ll t_, ll w_) { t = t_, w = w_; }
};
vector<edge> G[N];
struct node
{
ll id, d;
bool operator<(const node &x) const { return d > x.d; }
};
void dijkstra(ll s)
{
priority_queue<node> q;
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
q.push((node){s, 0});
for (node cur; !q.empty();)
{
cur = q.top();
q.pop();
ll u = cur.id;
if (cur.d > dis[u])
continue;
for (auto x : G[u])
if (dis[x.t] > dis[u] + x.w)
dis[x.t] = dis[u] + x.w, q.push((node){x.t, dis[x.t]});
}
}
int main()
{
yin >> n >> m >> s;
//建图
for (ll i = 1, u, v, w; i <= m; i++)
yin >> u >> v >> w, G[u].push_back(edge(v, w)), G[v].push_back(edge(u, w));
dijkstra(s);
for (ll u = 1; u <= n; u++)
for (auto v : G[u])
if (dis[v.t] == dis[u] + v.w)
es[v.t].push_back(u), d[v.t]++;
//最小支配树
for (ll i = 1; i <= n; i++)
if (!d[i])
es[i].push_back(n + 1);
for (ll i = 1; i <= n; i++)
if (!vst[i])
build(i);
dfs(n + 1);
ll ans = 0;
for (ll i = 1; i <= n; i++)
if (i != s)
ans = max(ans, sz[i]);
yout << ans << '\n';
return 0;
}
|
, $ 1<=s<=n $ ) — the number of cities and the number of roads in the Himalayan region and the city Bash lives in.