题解 CF757F 【Team Rocket Rises Again】

· · 题解

《关于我随机开 CF 然后刷到支配树模板自闭一万年这件事》

那么，如果像我一样，不会支配树也不想学怎么办呢？

提供一个时间复杂度 O(n+m\log n)（瓶颈在最短路），空间复杂度 O(n+m)，不需要支配树（我相信我没有自己发明），更不需要倍增 LCA 和 LCT 的做法。

（截至 2021.3.21，该做法在 CF 上是最优解。）（虽然可能是评测机进化了）

首先还是要跑一遍 Dijkstra，建出最短路 DAG。

问题变成删除除了 s 以外的一个点，使得 s 无法到达的点数尽可能多。

注意我们只需要求最大值，所以没有必要把每个点删掉都求一遍。

首先，如果一个点入度为 1 且它的入点不是 s，那么删它肯定不如删它的入点优。因为删掉它的入点后，它也无法被到达。也就是说一条“链”可以被缩成一个点。

那么做一遍拓扑排序，每次看所有入边的入点是否被缩成了同一个点。如果是，那么将当前点也缩进去。

缩完之后，每个点要么入度 \ge 2，要么入点是 s，要么自己就是 s。那么无论删掉哪个异于 s 的点，其它点都能从 s 到达。不能到达的只有当前点以及和它缩在一起的点。

对每个缩在一起的点集求大小最大值即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=666666,mod=998244353;
#define PB push_back
#define MP make_pair
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
    int x=0,f=0;char ch=getchar();
    while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
int n,m,s,el,head[maxn],to[maxn],nxt[maxn],w[maxn];
int el2,head2[maxn],to2[maxn],nxt2[maxn],deg[maxn];
int q[maxn],h,r,id[maxn],sz[maxn],ans,tmp[maxn];
ll dis[maxn];
struct node{
    ll d;
    int u;
    bool operator<(const node &nd)const{return d>nd.d;}
};
priority_queue<node> pq; 
inline void add(int u,int v,int ww){
    to[++el]=v;nxt[el]=head[u];head[u]=el;w[el]=ww;
}
inline void add2(int u,int v){
    to2[++el2]=v;nxt2[el2]=head2[u];head2[u]=el2;deg[v]++;
}
int main(){
    n=read();m=read();s=read();
    FOR(i,1,m){
        int u=read(),v=read(),w=read();
        add(u,v,w);add(v,u,w);
    }
    FOR(i,1,n) dis[i]=1e18;
    pq.push((node){dis[s]=0,s});
    while(!pq.empty()){
        int u=pq.top().u;
        ll d=pq.top().d;
        pq.pop();
        if(dis[u]!=d) continue;
        for(int i=head[u];i;i=nxt[i]){
            int v=to[i];
            if(d+w[i]<dis[v]) pq.push((node){dis[v]=d+w[i],v});
        }
    }
    FOR(u,1,n) for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(dis[u]+w[i]==dis[v]) add2(u,v);
    }
    q[h=r=1]=s;
    FOR(i,1,n) tmp[i]=i;
    while(h<=r){
        int u=q[h++];
        if(tmp[u]!=-1 && tmp[u]!=s) id[u]=tmp[u];
        else id[u]=u;
        sz[id[u]]++;
        for(int i=head2[u];i;i=nxt2[i]){
            int v=to2[i];
            if(tmp[v]==v) tmp[v]=id[u];
            else if(tmp[v]!=id[u]) tmp[v]=-1;
            if(!--deg[v]) q[++r]=v;
        }
    }
    FOR(i,1,n) if(i!=s) ans=max(ans,sz[i]);
    printf("%d\n",ans);
}