CF757F-Team Rocket Rises Again【最短路,DAG支配樹】

正題

題目連結:https://www.luogu.com.cn/problem/CF757F

題目大意

\(n\)個點\(m\)條邊的一張無向圖，求删除\(s\)以外的一個點改變\(s\)到最多點的最短路。

解題思路

挺裸的一道題的，首先肯定要跑一遍最短路搞出最短路樹。

然後如果最短路樹上\(s\)到某個點的路徑被割掉了就會改變最短路長度，是以直接求出支配樹然後看除了根以外最大子樹的子節點就好了。

時間複雜度\(O(m\log n)\)

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define mp(x,y) make_pair(x,y)
using namespace std;
const ll N=3e5+10,T=19;
priority_queue<pair<ll,ll>> q;
struct node{
    ll to,next,w;
}a[N*2];
ll n,m,s,tot,ls[N],dis[N],dep[N],v[N];
ll head,tail,top[N],f[N][T+1],siz[N];
void addl(ll x,ll y,ll w){
    a[++tot].to=y;
    a[tot].next=ls[x];
    ls[x]=tot;a[tot].w=w;
    return;
}
void dij(){
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;q.push(mp(0,s));
    while(!q.empty()){
        ll x=q.top().second;q.pop();
        if(v[x])continue;v[x]=1;
        for(ll i=ls[x];i;i=a[i].next){
            ll y=a[i].to;
            if(dis[x]+a[i].w<dis[y]){
                dis[y]=dis[x]+a[i].w;
                q.push(mp(-dis[y],y));
            }
        }
    }
    return;
}
ll LCA(ll x,ll y){
    if(dep[x]>dep[y])swap(x,y);
    for(ll i=T;i>=0;i--)
        if(dep[f[y][i]]>=dep[x])
            y=f[y][i];
    if(x==y)return x;
    for(ll i=T;i>=0;i--)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}
void build(){
    head=1;tail=1;top[1]=s;
    memset(v,0,sizeof(v));
    for(ll x=1;x<=n;x++)
        for(ll i=ls[x];i;i=a[i].next)
            if(dis[x]+a[i].w==dis[a[i].to])
                v[a[i].to]++;
    while(head<=tail){
        ll x=top[head++];
        dep[x]=dep[f[x][0]]+1;
        for(ll i=1;i<=T;i++)
            f[x][i]=f[f[x][i-1]][i-1];
        for(ll i=ls[x];i;i=a[i].next){
            ll y=a[i].to;
            if(dis[x]+a[i].w!=dis[y])continue;
            v[y]--;
            if(!f[y][0])f[y][0]=x;
            else f[y][0]=LCA(f[y][0],x);
            if(!v[y])top[++tail]=y;
        }
    }
    return;
}
signed main()
{
    scanf("%lld%lld%lld",&n,&m,&s);
    for(ll i=1;i<=m;i++){
        ll x,y,w;
        scanf("%lld%lld%lld",&x,&y,&w);
        addl(x,y,w);addl(y,x,w);
    }
    dij();
    build();ll ans=0;
    for(ll i=tail;i>1;i--){
        siz[top[i]]++,siz[f[top[i]][0]]+=siz[top[i]];
        ans=max(ans,siz[top[i]]);
    }
    printf("%lld\n",ans);
}