正題

題目鏈接:https://www.luogu.com.cn/problem/CF757F

---

題目大意

$n$個(gè)點(diǎn)$m$條邊的一張無(wú)向圖，求刪除$s$以外的一個(gè)點(diǎn)改變$s$到最多點(diǎn)的最短路。

---

解題思路

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

然后如果最短路樹(shù)上$s$到某個(gè)點(diǎn)的路徑被割掉了就會(huì)改變最短路長(zhǎng)度，所以直接求出支配樹(shù)然后看除了根以外最大子樹(shù)的子節(jié)點(diǎn)就好了。

時(shí)間復(fù)雜度$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); }

總結(jié)

以上是生活随笔為你收集整理的CF757F-Team Rocket Rises Again【最短路,DAG支配树】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。