CF757F Team Rocket Rises Again
全体起立，全体起立，这是我A的第一道黑题（虽然是CF的）；
来一波番茄攻击；
不扯淡了，这道题也是学习支配树（之前）应该做的题；
和灾难不同的是，那个是直接给你有向图，这里给的是无向图；
我们要求的是删除一个点会造成多少点的最短路发生变化，那么我们可以根据最短路再建一个有向图，这样就和灾难一样了；
很不幸，我建了四个图；
因为一开始写挂了所以图的编号是乱的；（这并不影响我AC）
add是无向图，add2是有向图，add4是反图，add3是建出来的支配树；
首先我们为什么要建反图：
{
一个点是否对其他的点有价值，就是看是否他在最短路径上；
我们根据有向图算出了拓扑序，拓扑序靠前的就是靠近起始点的；
我们需要建支配树，那么当前点要当谁的儿子？
当然是所有连向他的点的LCA，因为所有连向他的点删掉后（点数大于等于2）还可以在其他的点上走；
我们当初只建了一个有向图连向当前点，我们还要回去找LCA，所以要建一个反图；
}
然后子树大小即为答案；（取最大值）
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=3e5+;
int n,m,s;
int pre[maxn*],last[maxn],other[maxn*],l;
ll len[maxn*];
int pre2[maxn*],last2[maxn],other2[maxn*],l2;
int pre3[maxn*],last3[maxn],other3[maxn*],l3;
int pre4[maxn*],last4[maxn],other4[maxn*],l4;
void add(int x,int y,ll z)
{
l++;
pre[l]=last[x];
last[x]=l;
other[l]=y;
len[l]=z;
}
void add2(int x,int y)
{
l2++;
pre2[l2]=last2[x];
last2[x]=l2;
other2[l2]=y;
//len[l]=z;
} void add3(int x,int y)
{
l3++;
pre3[l3]=last3[x];
last3[x]=l3;
other3[l3]=y;
//len[l]=z;
}
void add4(int x,int y)
{
l4++;
pre4[l4]=last4[x];
last4[x]=l4;
other4[l4]=y;
}
priority_queue<pair<ll,int> > qq;
bool vis[maxn];
ll dis[maxn];
void dijkstra(int x)
{
memset(vis,,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
dis[x]=;
qq.push(make_pair(,x));
while(!qq.empty())
{
int u=qq.top().second;
qq.pop();
if(vis[u]) continue;
vis[u]=;
for(int p=last[u];p;p=pre[p])
{
int v=other[p];
if(dis[v]>dis[u]+len[p])
{
dis[v]=dis[u]+len[p];
qq.push(make_pair(-dis[v],v));
}
}
}
}
queue<int> q;
int topo[maxn],sum,in_eage[maxn];
void toposort()//此时用有向图找出拓扑序
{
for(int i=;i<=n;i++)
{
if(in_eage[i]==&&dis[i]!=dis[]) q.push(i);//此时要抛弃不在有向图上的点
}
while(!q.empty())
{
int x=q.front();
q.pop();
topo[++sum]=x;
for(int p=last2[x];p;p=pre2[p])
{
int v=other2[p];
in_eage[v]--;
if(in_eage[v]==)
{
q.push(v);
}
}
}
}
int father[maxn],f[maxn][];
int dep[maxn]; void rmq(int x)
{
f[x][]=father[x];
for(int i=;i<=;i++)
{
f[x][i]=f[f[x][i-]][i-];
}
} int LCA(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int j=;j<=;j++)
{
if((dep[x]-dep[y])&(<<j)) x=f[x][j];
}
if(x==y) return x;
for(int j=;j>=;j--)
{
if(f[x][j]!=f[y][j])
{
x=f[x][j];
y=f[y][j];
}
}
return father[x];
} void build()//重新建树的时候用反图
{
father[n+]=n+;//建立虚拟节点
f[n+][]=n+;
dep[n+]=;
for(int i=;i<=n;i++)//拓扑序从小到大开始遍历，根据反图，当前建的树的子树大小即为支配数
{
if(!topo[i]) break;//并不是所有点都在有向图上 ，但是图上的点拓扑序是连续的
int x=topo[i];
if(!last4[x])//将没有出边的点连上虚拟节点
{
dep[x]=;
father[x]=n+;
f[x][]=n+;
add3(n+,x);//3为生成的支配树
continue;
} int lca=other4[last4[x]];
for(int p=last4[x];p;p=pre4[p])
{
int v=other4[p];
lca=LCA(lca,v);
}
father[x]=lca;
dep[x]=dep[lca]+;
add3(lca,x);
rmq(x);
}
} int siz[maxn];
int ans;
void dfs(int x)
{
siz[x]=;
for(int p=last3[x];p;p=pre3[p])
{
int v=other3[p];
dfs(v);
siz[x]+=siz[v];
}
if(x!=n+&&x!=s) ans=max(ans,siz[x]);
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
for(int i=;i<=m;i++)
{
int x,y;ll z;
scanf("%d%d%lld",&x,&y,&z);
add(x,y,z);
add(y,x,z);//建无向图
}
dijkstra(s);//求最短路
for(int i=;i<=n;i++)
{
for(int p=last[i];p;p=pre[p])
{
int v=other[p];
if(dis[v]==dis[i]+len[p])
{
add2(i,v);//根据最短路建立有向图
add4(v,i); //反图
in_eage[v]++;//rudu
}
}
}
toposort();
build();
dfs(n+);
printf("%d",ans);
return ;
}