首页 > 代码库 > codeforces 757F Team Rocket Rises Again

codeforces 757F Team Rocket Rises Again

2024-09-08 21:18:06   219人阅读

链接：http://codeforces.com/problemset/problem/757/F

正解：灭绝树。

mdzz倍增lca的根节点深度必须是1。。我因为这个错误调了好久。

我们考虑先求最短路，求完最短路以后，我们就能对原来的无向图构造一个DAG。当我们构造完DAG以后，我们要求的东西已经很明显。那就是删掉一个点以后，最多有多少个点与S不连通。那么，我们按照套路，将DAG跑一遍拓扑排序，建出灭绝树。然后求出除了S点以外的最大size就行了。

 

  1 //It is made by wfj_2048~  2 #include <algorithm>  3 #include <iostream>  4 #include <complex>  5 #include <cstring>  6 #include <cstdlib>  7 #include <cstdio>  8 #include <vector>  9 #include <cmath> 10 #include <queue> 11 #include <stack> 12 #include <map> 13 #include <set> 14 #define inf (1LL<<60) 15 #define M (300010) 16 #define N (200010) 17 #define il inline 18 #define RG register 19 #define ll long long 20 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) 21  22 using namespace std; 23  24 struct edge{ int nt,to; ll dis; }g[2*M],g1[2*M],g2[2*M]; 25  26 int head[N],head1[N],head2[N],q[20*N],d[N],vis[N],dep[N],sz[N],f[22][N],S,n,m,num,num1,num2,ans; 27 ll dis[N]; 28  29 il int gi(){ 30     RG int x=0,q=1; RG char ch=getchar(); while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar(); 31     if (ch==‘-‘) q=-1,ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar(); return q*x; 32 } 33  34 il void insert(RG int from,RG int to,RG ll dis){ g[++num]=(edge){head[from],to,dis},head[from]=num; return; } 35  36 il void insert1(RG int from,RG int to){ g1[++num1]=(edge){head1[from],to},head1[from]=num1; return; } 37  38 il void insert2(RG int from,RG int to){ g2[++num2]=(edge){head2[from],to},head2[from]=num2; return; } 39  40 il void spfa(RG int S){ 41     for (RG int i=1;i<=n;++i) dis[i]=inf; 42     RG int h=0,t=1; dis[S]=0,vis[S]=1,q[t]=S; 43     while (h<t){ 44     RG int x=q[++h]; 45     for (RG int i=head[x],v=g[i].to;i;i=g[i].nt,v=g[i].to) 46         if (dis[v]>dis[x]+g[i].dis){ 47         dis[v]=dis[x]+g[i].dis; 48         if (!vis[v]) vis[v]=1,q[++t]=v; 49         } 50     vis[x]=0; 51     } 52     return; 53 } 54  55 il void dfs1(RG int x){ 56     vis[x]=1; 57     for (RG int i=head[x],v=g[i].to;i;i=g[i].nt,v=g[i].to) 58     if (dis[v]==dis[x]+g[i].dis){ 59         insert1(x,v),insert2(v,x),d[v]++; 60         if (!vis[v]) dfs1(v); 61     } 62     return; 63 } 64  65 il void dfs2(RG int x){ 66     sz[x]=1; RG int v; 67     for (RG int i=head[x];i;i=g[i].nt) 68     v=g[i].to,dfs2(v),sz[x]+=sz[v]; 69     if (x!=S) ans=max(ans,sz[x]); return; 70 } 71  72 il int lca(RG int u,RG int v){ 73     if (u==v) return u; if (dep[u]<dep[v]) swap(u,v); 74     for (RG int i=20;i>=0;--i) 75     if (dep[f[i][u]]>=dep[v]) u=f[i][u]; 76     if (u==v) return u; 77     for (RG int i=20;i>=0;--i) 78     if (f[i][u]!=f[i][v]) u=f[i][u],v=f[i][v]; 79     return f[0][u]; 80 } 81  82 il void topsort(){ 83     RG int h=0,t=1; q[t]=S,dep[S]=1; //不赋初值会跪烂！！！ 84     while (h<t){ 85     RG int x=q[++h],v; 86     for (RG int i=head1[x];i;i=g1[i].nt){ 87         v=g1[i].to,d[v]--; 88         if (!d[v]){ 89         q[++t]=v; RG int Lca=0; 90         for (RG int j=head2[v];j;j=g2[j].nt) 91             if (!Lca) Lca=g2[j].to; else Lca=lca(Lca,g2[j].to); 92         insert(Lca,v,0),f[0][v]=Lca,dep[v]=dep[Lca]+1; 93         for (RG int j=1;j<=20;++j) f[j][v]=f[j-1][f[j-1][v]]; 94         } 95     } 96     } 97     return; 98 } 99 100 il void work(){101     n=gi(),m=gi(),S=gi();102     for (RG int i=1,u,v,w;i<=m;++i){103     u=gi(),v=gi(),w=gi();104     insert(u,v,(ll)w),insert(v,u,(ll)w);105     }106     spfa(S); dfs1(S); memset(head,0,sizeof(head)),num=0;107     topsort(); dfs2(S); printf("%d\n",ans); return;108 }109 110 int main(){111     File("757F");112     work();113     return 0;114 }

 

codeforces 757F Team Rocket Rises Again


联系
我们