题解 P2597 【[ZJOI2012]灾难】

· · 题解

[P2597 [ZJOI2012]灾难]

传送门

前言

感谢 lzx 巨佬。

这道题在我AC之前，这位巨佬和我已经讨论了一个礼拜。

多亏他的无数次WA与TLE 我们最终想出了正解。

题目分析

首先先要建一个有向森林。

我们再想，如果这条食物链是一棵树。

但样例的图片一看就知道题目并没有那么简单毕竟是一道紫题。

如果你想由一个点灭绝来推导，那么恭喜，你走入了一条死路。

反过来想，一个点灭绝原因。

发现，一个点灭绝的前提是，所有前驱都灭绝。

一次只能灭绝一个。

如果前驱多个的话，显然灭绝一个该点不会灭绝。

所以，继续找前驱的前驱。

直到前驱变成一个点P。那么，就相当于，这个点灭绝了，开始说的点X才会灭绝。

如果我们构造出来一个树，那么这个P就是X的所有前驱的LCA

找到所有前驱的LCA，直接把X作为LCA的儿子连上去。就构造出来了这个树。

其实，就是最近的可以灭绝后灭绝X的点。

那它每个节点的灾难值就是它的子树大小-1。

但是 也会出现一个生物吃两个生产者的情况，这时LCA便会出现BUG，就需要建一个超级原点ROOT，把所有入度为0的点（根）都接上去，就可以用LCA了。

root不参与答案统计。如果连向root的点，无论如何不会因为某个物种灭绝而灭绝。（因为多于一个前驱必须自己死）

上代码：

#include<bits/stdc++.h>
#define res register int
#define maxn 500010
using namespace std;
void read(int &x) {
    int f = 1; x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')   {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    x *= f;
}
struct node{int to,nxt;};
node edge[maxn<<1],edge2[maxn<<1];int indegree[maxn],dad[maxn];
int head[maxn],head2[maxn],m,n,root,dep[maxn],fa[maxn][30],num,sum,siz[maxn],topo[maxn];
void add1(int a,int b){edge[++num].to=b;edge[num].nxt=head[a];head[a]=num;indegree[b]++;}
void add2(int a,int b){edge2[++num].to=b;edge2[num].nxt=head2[a];head2[a]=num;}
int lca(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    for(res i=20;i>=0;--i)if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
    if(u==v) return u;
    for(res i=20;i>=0;--i)if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
void get_siz(int x){//求子树大小 
    for(res i=head2[x];i!=-1;i=edge2[i].nxt){
        int y=edge2[i].to;get_siz(y);siz[x]+=siz[y];
    }
}
void topsort()
{
    memset(dad,-1,sizeof(dad));
    queue< int > q;
    for(int i=1;i<=n;i++) if(!indegree[i])q.push(i),dad[i]=0;
    while(!q.empty())
    {
        int temp=q.front();q.pop();
        add2(dad[temp],temp);dep[temp]=dep[dad[temp]]+1;
        fa[temp][0]=dad[temp];
        for(int i=1;i<=16;i++)fa[temp][i]=fa[fa[temp][i-1]][i-1];
        for(int p=head[temp];p!=-1;p=edge[p].nxt)
        {
            int v=edge[p].to;
            if(dad[v]==-1) dad[v]=temp;
            else dad[v]=lca(dad[v],temp);
            indegree[v]--;
            if(!indegree[v])q.push(v);

        }
    }
}
int main(){
    read(n);
    memset(head,-1,sizeof(head));
    memset(indegree,0,sizeof(indegree));
    for(int i=1,x;i<=n;i++){//节点数 
        while(1){
            read(x);
            if(!x) break;
            add1(x,i);
        }
    }
    siz[0]=dep[0]=0;memset(head2,-1,sizeof(head2));
    topsort();get_siz(0);
    for(int i=1;i<=n;i++)printf("%d\n",siz[i]-1);
    return 0;
}

总结

突破口就是想到转化成树比较好处理。然后考虑一个物种是怎么灭绝的。

发现，一个物种灭绝，只要找到最近的可以让它灭绝的物种Y即可。所有能让Y灭绝的物种也能让X灭绝。

而一个物种灭绝后，可能影响到多个物种也灭绝。

一个点，一个前驱，多个后继。

这就是树形结构！！

根据其他巨佬的题解，原来这还是DAG的支配树

所以其实是模板题。（惊了！）

求点赞