• 周四. 4月 25th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

【BZOJ】2815: [ZJOI2012]灾难

admin

11月 28, 2021

简要题意:

给一个有向无环图,问每个节点删掉之后会导致多少个点不可达。

似乎以前拿来考过….

我们定义一棵树,它满足对应点造成的灭绝值即为当点的子树大小-1

  按照被捕食者—>捕食者的关系拓扑排序,然后依次建树,建到当前点的时候可以作为当前生物食物的点应当已经在树中了。如果当前点代表的生物要灭亡,很好理解那么可以作为它食物的生物都要灭亡,所以将这个点丢到它的可以作为它食物的生物的所有点的最近$LCA$点之下就可以了,可以用倍增$LCA$来维护动态加点。

  为了方便,可以令一个点作为所有生产者的根。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<vector>
  5 #include<cstdlib>
  6 #include<cmath>
  7 #include<cstring>
  8 using namespace std;
  9 #define maxn 100100
 10 #define llg int
 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
 12 llg n,m,e[maxn],du[maxn],dl[maxn],tpx[maxn],deep[maxn],f[maxn][22],size[maxn];
 13 vector<llg>a[maxn],c[maxn],g[maxn];
 14 void in(llg x)
 15 {
 16     llg d;
 17     while (1)
 18     {
 19         scanf("%d",&d);
 20         if (d==0) break;
 21         du[x]++;
 22         a[d].push_back(x);
 23         c[x].push_back(d);
 24     }
 25 }
 26 
 27 void TP()
 28 {
 29     dl[1]=n+1;
 30     llg head=0,tail=1,x,v,w,cnt=0;
 31     do
 32     {
 33         x=dl[++head];
 34         w=a[x].size();
 35         tpx[x]=++cnt;
 36         for (llg i=0;i<w;i++)
 37         {
 38             v=a[x][i];
 39             du[v]--;
 40             if (du[v]==0)
 41             {
 42                 dl[++tail]=v;
 43             }
 44         }
 45     }while (head!=tail);
 46 }
 47 
 48 bool cmp(llg a,llg b){return tpx[a]<tpx[b];}
 49 
 50 void make_f(llg x) {for (llg i=1;i<=20;i++) f[x][i]=f[f[x][i-1]][i-1];}
 51 
 52 llg find(llg x,llg y)
 53 {
 54     if (deep[x]<deep[y]) swap(x,y);
 55     for (llg i=20;i>=0;i--)
 56         if (deep[f[x][i]]>=deep[y])
 57             x=f[x][i];
 58     if (x==y) return x;
 59     for (llg i=20;i>=0;i--)
 60         if (f[x][i]!=f[y][i])
 61             x=f[x][i],y=f[y][i];
 62     return f[x][0];
 63 }
 64 
 65 void work(llg x)
 66 {
 67     llg ro;
 68     if (c[x].size()==1) ro=c[x][0];
 69     else
 70     {
 71         llg w=c[x].size();
 72         ro=find(c[x][1],c[x][0]);
 73         for (llg i=2;i<w;i++) ro=find(ro,c[x][i]);
 74     }
 75     f[x][0]=ro; deep[x]=deep[ro]+1;
 76     g[ro].push_back(x);
 77     make_f(x);
 78 }
 79 
 80 void dfs(llg x)
 81 {
 82     llg w=g[x].size();
 83     size[x]=1;
 84     for (llg i=0;i<w;i++)
 85     {
 86         dfs(g[x][i]);
 87         size[x]+=size[g[x][i]];
 88     }
 89 }
 90 
 91 int main()
 92 {
 93     yyj("catas");
 94     cin>>n;
 95     for (llg i=1;i<=n;i++) in(i);
 96     for (llg i=1;i<=n;i++) 
 97         if (du[i]==0)
 98         {
 99             du[i]++;
100             c[i].push_back(n+1);
101             a[n+1].push_back(i);
102         }
103     TP();
104     for (llg i=1;i<=n+1;i++) e[i]=i;
105     sort(e+1,e+n+1,cmp);
106     deep[n+1]=1;
107     for (llg i=1;i<=n;i++) 
108         work(e[i]);
109     dfs(n+1);
110     for (llg i=1;i<=n;i++) printf("%d
",size[i]-1);
111     return 0;
112 }

《【BZOJ】2815: [ZJOI2012]灾难》有6个想法
  1. Heya i’m for the primary time here. I came across this board and I in finding It truly helpful &
    it helped me out much. I’m hoping to offer one thing back
    and aid others such as you helped me. I saw similar here:
    Dobry sklep

  2. Howdy! I could have sworn I’ve been to this website before but after browsing through a few of the posts I realized it’s new to me.
    Anyways, I’m certainly happy I came across it and I’ll be
    bookmarking it and checking back regularly! I saw similar here: Dobry sklep

  3. Hey! Do you know if they make any plugins to help with Search Engine Optimization? I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very
    good results. If you know of any please share.
    Thanks! You can read similar blog here: Sklep

  4. Howdy! Do you know if they make any plugins to help with SEO?
    I’m trying to get my site to rank for some targeted keywords but I’m not seeing very good success.
    If you know of any please share. Cheers! You can read similar
    article here: AA List

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注