相关链接
题目传送门:http://codeforces.com/problemset/problem/757/F
官方题解:http://codeforces.com/blog/entry/49743
中文题面及题解:https://blog.sengxian.com/solutions/cf-757f
解题报告
先搞出一个最短路径树,然后把一些非树边也给搞进来
我们发现这货是一个DAG,那么问题就转化为了:
给定一个DAG,问删掉一个点,最多使得多少点不可到达
然后我们就会想起这个题:BZOJ 2851
于是我们搞一个灾难树就可以啦!
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 200000+9; const int M = 600000+9; const LL INF = 1e9 * 1e9; LL dis[N]; int n,m,s,E,vout,fa[N][20],done[N],in[N]; int head[N],to[M],nxt[M],cost[M],dep[N]; priority_queue<pair<LL,int> > que; vector<int> anc[N],son[N]; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } inline void Add_Edge(int u, int v, int c = 0) { to[++E] = v; nxt[E] = head[u]; head[u] = E; cost[E] = c; to[++E] = u; nxt[E] = head[v]; head[v] = E; cost[E] = c; } inline void Dijkstra() { memset(dis,60,sizeof(dis)); dis[s] = 0; que.push(make_pair(0, s)); while (!que.empty()) { int w = que.top().second; que.pop(); if (!done[w]) done[w] = 1; else continue; for (int i=head[w];i;i=nxt[i]) { if (dis[to[i]] > dis[w] + cost[i]) { dis[to[i]] = dis[w] + cost[i]; que.push(make_pair(-dis[to[i]], to[i])); } } } } inline int LCA(int u, int v) { if (dep[u] < dep[v]) swap(u, v); for (int i=19;~i;i--) if (dep[fa[u][i]] >= dep[v]) u = fa[u][i]; if (u == v) return u; for (int i=19;~i;i--) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i]; return fa[u][0]; } void solve(int w) { done[w] = 1; int f = anc[w][0]; for (int i=1;i<(int)anc[w].size();i++) f = LCA(f, anc[w][i]); Add_Edge(f, w); fa[w][0] = f; dep[w] = dep[f] + 1; for (int i=1;i<20;i++) fa[w][i] = fa[fa[w][i-1]][i-1]; for (int i=son[w].size()-1,t;~i;i--) { t = son[w][i]; if (--in[t] == 0 && !done[t]) { solve(t); } } } int DFS(int w, int f) { int sz = 1; for (int i=head[w];i;i=nxt[i]) { if (to[i] != f) { sz += DFS(to[i], w); } } if (w != s) vout = max(vout, sz); return sz; } int main() { n = read(); m = read(); s = read(); for (int i=1,u,v;i<=m;i++) { u = read(); v = read(); Add_Edge(u, v, read()); } Dijkstra(); for (int w=1;w<=n;w++) { if (dis[w] > INF) continue; for (int i=head[w];i;i=nxt[i]) { if (dis[to[i]] == dis[w] + cost[i]) { anc[to[i]].push_back(w); son[w].push_back(to[i]); in[to[i]] += (w != s); } } } memset(head,0,sizeof(head)); memset(done,0,sizeof(done)); done[s] = 1; E = 0; for (int i=0;i<20;i++) fa[s][i] = s; for (int i=1;i<=n;i++) { if (!in[i] && !done[i] && dis[i] < INF) { solve(i); } } DFS(s, s); printf("%d\n",vout); return 0; }