bzoj 2815

http://www.cnblogs.com/JS-Shining/archive/2013/01/12/2857429.html 题面

题解上写了用什么dominator tree，吓晕了，看了看，好像看不懂，于是看了看hzwer的代码，发现和dominator tree无半点关系。

-----------------------------------------------------------------------------------------------------------------------------------

首先我们假设有一个太阳，就是所有没有食物的物种的食物。

然后我们想一下如果一个物种要灭绝，那么他的食物得先灭绝。他的食物怎么会灭绝？那么他的食物的食物也得灭绝，最后这些食物的根源肯定会汇集到一个点上，也就是所有食物得lca（你想啊一棵树上几个点不断往上爬肯定会汇集到一个点上（其实我也不太懂））。首先我们得拓扑排序一下，因为拓扑排序让一个物种能处于他的食物以及食物的食物之后（之后是指顺序上，也就是保证先处理好了自己食物及食物得的食物等，再处理自己）。然后扫描拓扑排序后的物种，对于每个物种，找他食物的lca，如果原图中没有食物，我们搞的太阳就变成了它的食物，然后把这个物种放在lca下面。这棵树可以帮我们统计答案，因为树的节点的儿子都是这个节点灭绝后会导致灭绝的物种。为什么放在lca下可以呢？因为我们要找lca的目的在于找到哪个物种能让自己灭绝，又因为lca能让这个物种灭绝，所以放在下面是对的。如何统计答案呢？因为每个点下挂的节点都是自己的灭绝能让他也灭绝，自己的儿子也是这样，所以以每个节点的子树大小-1就是答案。-1是把自己减去。

（我的代码是不是跟hzwer的很像？因为我看了他的，深受影响）还说一个可能的问题，为什么两个图能共用一个e数组？因为他们的head不一样

#include<bits/stdc++.h>

using namespace std;

#define N 100010

struct edge

{

    int nxt,to;

}e[N<<];

int n,cnt=;

vector<int> q,s;

struct G

{

    int dep[N],head[N],size[N],in[N];

    int fa[N][];

    void init()

    {

        memset(fa,-,sizeof(fa));

    }

    void link(int u,int v)

    {

        e[++cnt].nxt=head[u];

        head[u]=cnt;

        e[cnt].to=v;

        in[v]++;

    }

    int lca(int u,int v)

    {

        if(u==-) return v;

        if(v==-) return u;

        if(dep[u]<dep[v]) swap(u,v);

        int temp=dep[u]-dep[v];

        for(int i=;i>=;--i) if(temp&(<<i))

            u=fa[u][i];

        if(u==v) return u;

        for(int i=;i>=;--i) if(fa[u][i]!=fa[v][i])

        {

            u=fa[u][i]; v=fa[v][i];

        }

        return fa[u][];

    }

    void dfs(int u)

    {

        size[u]=;

        for(int i=head[u];i;i=e[i].nxt)

        {

            dfs(e[i].to);

            size[u]+=size[e[i].to];

        }

    }

    void tp()

    {

        for(int i=;i<=n;++i) if(!in[i]) q.push_back(i);

        while(!q.empty())

        {

            int u=q.back(); q.pop_back(); s.push_back(u);

            for(int i=head[u];i;i=e[i].nxt)

            {

                in[e[i].to]--;

                if(!in[e[i].to]) q.push_back(e[i].to);

            }

        }

    }

    void update(int u)

    {

        for(int i=;i<=;++i) if(fa[u][i-])

            fa[u][i]=fa[fa[u][i-]][i-];

    }

}G1,G2;

void build_tree()

{

    for(int i=s.size()-;i>=;--i)

    {

        int u=s[i],lca=-;

        for(int j=G1.head[u];j;j=e[j].nxt)

            lca=G2.lca(e[j].to,lca);

        if(lca==-) lca=;

        G2.link(lca,u);

        G2.fa[u][]=lca;

        G2.dep[u]=G2.dep[lca]+;

        G2.update(u);

    }

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;++i)

    {

        int x; scanf("%d",&x);

        while(x)

        {

            G1.link(i,x);

            scanf("%d",&x);

        }

    }

    G1.tp();

    build_tree();

    G2.dfs();

    for(int i=;i<=n;++i)

    {

        if(G2.size[i]) printf("%d\n",G2.size[i]-);

        else puts("");

    }

    return ;

}

巴特西

bzoj 2815

最新文章

热门文章