Codeforces

Luogu

分析

容易想到建出最短路图,问题变为求最短路图上去掉一个点后有多少个点无法到达。

这是一个经典问题([ZJOI2012]灾难),直接建出支配树即可。题解

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10,M=600000+10;

int n,m,s;
int x[M],y[M],l[M];
int id[M],sum[M],ans[N];

struct edge { int v,w,nxt; };
struct Graph {
    edge e[M]; int head[N],ecnt;
    Graph() { memset(head,0,sizeof(head)); ecnt=0; }
    void addEdge(int u,int v,int w=0) {
        e[++ecnt]=(edge){v,w,head[u]},head[u]=ecnt;
    }
} O,G,T;

struct node { int u; ll d; };
bool operator <(node a,node b) { return a.d>b.d; }
ll dis[N];
void dijkstra() {
    memset(dis,0x3f,sizeof(dis));
    priority_queue<node> Q; Q.push((node){s,0}); dis[s]=0;
    while (!Q.empty()) {
        int u=Q.top().u; ll d=Q.top().d; Q.pop();
        if (d!=dis[u]) continue;
        for (int i=O.head[u];i;i=O.e[i].nxt) {
            int v=O.e[i].v,w=O.e[i].w;
            if (dis[u]+w<dis[v])
                dis[v]=dis[u]+w,Q.push((node){v,dis[v]});
        }
    }
}

namespace DT {
int deg[N],fa[N],f[18][N],dep[N],sz[N];

int getlca(int u,int v) {
    if (dep[u]<dep[v]) swap(u,v);
    for (int i=17;~i;--i)
        if (dep[f[i][u]]>dep[v]) u=f[i][u];
    if (dep[u]!=dep[v]) u=f[0][u];
    for (int i=17;~i;--i)
        if (f[i][u]!=f[i][v]) u=f[i][u],v=f[i][v];
    if (u!=v) u=f[0][u];
    return u;
}

void dfs(int u) {
    sz[u]=dis[u]!=dis[0];
    for (int i=T.head[u];i;i=T.e[i].nxt)
        dfs(T.e[i].v),sz[u]+=sz[T.e[i].v];
}

void build() {
    queue<int> Q; memset(fa,-1,sizeof(fa));
    for (int i=1;i<=n;++i)
        if (!deg[i]) fa[i]=0,Q.push(i);
    while (!Q.empty()) {
        int u=Q.front(); Q.pop();
        dep[u]=dep[fa[u]]+1,T.addEdge(fa[u],u);
        f[0][u]=fa[u];
        for (int i=1;i<18;++i) f[i][u]=f[i-1][f[i-1][u]];
        for (int i=G.head[u];i;i=G.e[i].nxt) {
            int v=G.e[i].v;
            if (fa[v]==-1) fa[v]=u;
            else fa[v]=getlca(fa[v],u);
            if (!--deg[v]) Q.push(v); 
        }
    }
}
} // namespace DT

int main() {
    n=read(),m=read(),s=read();
    for (int i=1;i<=m;++i) {
        x[i]=read(),y[i]=read(),l[i]=read();
        O.addEdge(x[i],y[i],l[i]),O.addEdge(y[i],x[i],l[i]);
    }
    dijkstra();
    for (int i=1;i<=m;++i) {
        if (dis[x[i]]+l[i]==dis[y[i]])
            G.addEdge(x[i],y[i]),++DT::deg[y[i]];
        if (dis[y[i]]+l[i]==dis[x[i]])
            G.addEdge(y[i],x[i]),++DT::deg[x[i]];
    }
    DT::build(); DT::dfs(0); int ans=0;
    for (int i=1;i<=n;++i) 
        if (i!=s) ans=max(ans,DT::sz[i]);
    printf("%d\n",ans);
    return 0;
}
最后修改:2020 年 04 月 12 日 09 : 01 PM