题目
题目链接:https://codeforces.com/problemset/problem/757/F
给定一个 \(n\) 个点,\(m\) 条边的带权无向图,和起点 \(s\)。
选择一个点 \(u\)(\(u \neq S\)),使在图中删掉点 \(u\) 后,有尽可能多的点到 \(s\) 的最短距离改变。
\(1 \leq n \leq 2 \times 10^5\),\(1 \leq m \leq 3 \times 10^5\),给出的图无重边无自环,不保证连通。
思路
一遍 dij 求出最短路树,可以将原图简化成一张 DAG,其中如果一个点 \(x\) 能走到点 \(y\),那么删去 \(x\) 之后 \(S\) 到 \(y\) 的最短路就会边长。
那么构出支配树,在不为根的所有点的子树内求大小的最大值即可。
时间复杂度 \(O(n\log n)\)。
代码
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
typedef long long ll;
const int N=300010,LG=20;
int n,m,S,tot,ans,head[N],deg[N],dep[N],siz[N],f[N][LG+1];
ll dis[N];
bool vis[N];
struct edge
{
int next,to,dis;
}e[N*2];
void add(int from,int to,int dis)
{
e[++tot]=(edge){head[from],to,dis};
head[from]=tot;
}
int lca(int x,int y)
{
if (dep[x]<dep[y]) swap(x,y);
for (int i=LG;i>=0;i--)
if (dep[f[x][i]]>=dep[y]) x=f[x][i];
if (x==y) return x;
for (int i=LG;i>=0;i--)
if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
void dij()
{
memset(dis,0x3f3f3f3f,sizeof(dis));
priority_queue<pair<ll,int> > q;
q.push(mp(0,S)); dis[S]=0;
while (q.size())
{
int u=q.top().second; q.pop();
if (vis[u]) continue;
vis[u]=1;
for (int i=head[u];~i;i=e[i].next)
{
int v=e[i].to;
if (dis[v]>dis[u]+e[i].dis)
{
dis[v]=dis[u]+e[i].dis; deg[v]=0;
q.push(mp(-dis[v],v));
}
if (dis[v]==dis[u]+e[i].dis) deg[v]++;
}
}
}
void topsort()
{
queue<int> q;
q.push(S); f[S][0]=0;
while (q.size())
{
int u=q.front(); q.pop();
dep[u]=dep[f[u][0]]+1;
for (int i=1;i<=LG;i++)
f[u][i]=f[f[u][i-1]][i-1];
for (int i=head[u];~i;i=e[i].next)
{
int v=e[i].to;
if (dis[v]==dis[u]+e[i].dis)
{
if (f[v][0]==-1) f[v][0]=u;
else f[v][0]=lca(f[v][0],u);
deg[v]--;
if (!deg[v]) q.push(v);
}
}
}
}
void dfs(int x)
{
siz[x]=1;
for (int i=head[x];~i;i=e[i].next)
{
int v=e[i].to;
if (v!=f[x][0])
{
dfs(v);
siz[x]+=siz[v];
}
}
if (x!=S && ans<siz[x]) ans=siz[x];
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d%d",&n,&m,&S);
for (int i=1,x,y,z;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z); add(y,x,z);
}
for (int i=1;i<=n;i++) f[i][0]=-1;
dij(); topsort();
memset(head,-1,sizeof(head));
tot=0;
for (int i=1;i<=n;i++)
add(f[i][0],i,0);
dfs(S);
printf("%d",ans);
return 0;
}