HDU 3639 Hawk-and-Chicken(强连通分量+缩点)

http://acm.hdu.edu.cn/showproblem.php?pid=3639

题意:

给你一个有向图,如果从u点能到达v点,那么说u是v的粉丝,如今要你按序输出那些粉丝数目最多的点编号.

分析:

如果该图是一个强连通图,那么任一点都有n-1个粉丝(即n-1个点能到达它).所以我们把该图缩点变成一个新的DAG图.

结论:原图中具有最多粉丝的点一定在新图的那些出度为0的点所代表的分量中.

证明:如果u节点粉丝最多且它所属的分量出度不为0,那么u节点一定是某个节点v的粉丝,所以v的粉丝必定包括了u的全部粉丝加上u本身.所以v的粉丝必定多余u.由此矛盾.

以下的问题是怎样找新DAG图的每一个节点(所代表分量中的原节点)的最大粉丝数?

该粉丝数=本连通分量的点数-1+本连通分量能通过ß这样的边逆向走到的全部分量的点数和. 所以我们直接建立缩点树的逆图DAG就可以,如果u->v表示u分量将获得v分量的全部节点作为粉丝.所以我们仅仅须要对那几个入度为0的点做DFS就可以.

每次DFS到一个新节点,该点所代表的分量节点数就都加到sum上去,表示新加了非常多粉丝.最后找最大粉丝值的分量点输出就可以.

AC代码:

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<stack>

using namespace std;

const int maxn= 5000+10;

int n,m;

vector<int> G[maxn], G2[maxn];

stack<int> S;

int dfs_clock, scc_cnt;

int pre[maxn],sccno[maxn],low[maxn];

int num[maxn];//表每一个强连通分量各含多少点

int in[maxn];//新DAG的逆图中点的入度

int fan[maxn];//表新DAG中第i个点(分量)有多少粉丝

void dfs(int u)

{

    pre[u]=low[u]=++dfs_clock;

    S.push(u);

    for(int i=0;i<G[u].size();i++)

    {

        int v=G[u][i];

        if(!pre[v])

        {

            dfs(v);

            low[u]=min(low[u],low[v]);

        }

        else if(!sccno[v])

            low[u]=min(low[u],pre[v]);

    }

    if(low[u]==pre[u])

    {

        scc_cnt++;

        num[scc_cnt]=0;

        while(true)

        {

            int x=S.top(); S.pop();

            sccno[x]=scc_cnt;

            num[scc_cnt]++;

            if(x==u) break;

        }

    }

}

void find_scc(int n)

{

    dfs_clock=scc_cnt=0;

    memset(pre,0,sizeof(pre));

    memset(sccno,0,sizeof(sccno));

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

        if(!pre[i]) dfs(i);

}

bool vis[maxn];

int dfs2(int u)

{

    vis[u]=true;

    int sum=0;

    for(int i=0;i<G2[u].size();i++)

    {

        int v=G2[u][i];

        if(!vis[v]) sum+=num[v]+dfs2(v);  //WA-> vis[i] num[i] dfs2(i)

    }

    return sum;

}

int main()

{

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

    for(int kase=1;kase<=T;kase++)

    {

        scanf("%d%d",&n,&m);

        for(int i=0;i<n;i++) G[i].clear();

        while(m--)

        {

            int u,v;

            scanf("%d%d",&u,&v);

            G[u].push_back(v);

        }

        find_scc(n);

        memset(in,0,sizeof(in));

        for(int i=1;i<=scc_cnt;i++) G2[i].clear();

        for(int u=0;u<n;u++)

        for(int i=0;i<G[u].size();i++)

        {

            int v=G[u][i];

            int x=sccno[u], y=sccno[v];

            if(x!=y)

            {

                in[x]++;

                G2[y].push_back(x);//建立DAG的逆图

            }

        }

        memset(fan,0,sizeof(fan));

        int max_f=-1;

        for(int i=1;i<=scc_cnt;i++)

            if(!in[i])

            {

                memset(vis,0,sizeof(vis)); //WA-> vis数组仅仅在外面初始化1次

                fan[i] = num[i]-1+dfs2(i);

                max_f=max(fan[i],max_f);

            }

        bool win[maxn];

        memset(win,0,sizeof(win));

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

            if(fan[sccno[i]]==max_f) win[i]=true;

        printf("Case %d: %d\n",kase,max_f);

        bool first=true;

        for(int i=0;i<n;i++)if(win[i])

        {

            if(first) printf("%d",i), first=false;

            else printf(" %d",i);

        }

        puts("");

    }

    return 0;

}

秒客网

HDU 3639 Hawk-and-Chicken(强连通分量+缩点)

相关文章