题解 CF757F 【Team Rocket Rises Again】
AThousandSuns
2021-03-21 09:32:13
《关于我随机开 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$ 到达。不能到达的只有当前点以及和它缩在一起的点。
对每个缩在一起的点集求大小最大值即可。
```cpp
#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);
}
```