洛谷 P3225 [HNOI2012]矿场搭建 题解【tarjan】【连通图】

点击量：701

目录

题目描述

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。

 

请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

输入输出格式

输入格式：

输入文件有若干组数据，每组数据的第一行是一个正整数 N（N<=500），表示工地的隧道数，接下来的 N 行每行是用空格隔开的两个整数 S 和 T，表示挖煤点 S 与挖煤点 T 由隧道直接连接。输入数据以 0 结尾。

 

输出格式：

输入文件中有多少组数据，输出文件 output.txt 中就有多少行。每行对应一组输入数据的 结果。其中第 i 行以 Case i: 开始（注意大小写，Case 与 i 之间有空格，i 与:之间无空格，: 之后有空格），其后是用空格隔开的两个正整数，第一个正整数表示对于第 i 组输入数据至少需要设置几个救援出口，第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总 数。输入数据保证答案小于 2^64。输出格式参照以下输入输出样例。

 

输入输出样例

输入样例#1：

9

1 3

4 1

3 5

1 2

2 6

1 5

6 3

1 6

3 2

6

1 2

1 3

2 4

2 5

3 6

3 7

0

输出样例#1：

Case 1: 2 4

Case 2: 4 1

说明

Case 1 的四组解分别是(2,4),(3,4),(4,5),(4,6)；

Case 2 的一组解为(4,5,6,7)。

   矿点坍塌我们可以抽象为将这个点删去。设图中原来有k个联通块，如果删掉割点，那么现在就有了k+1个联通块，如果不是割点，联通块数目不变。因此我们可以看出，割去任一个割点，割点两边的联通块都需要设一个逃生口。（关于怎么求割点）我们先来分析几个情况：

1.链上

   可以看出，图中有5个割点：2，3，4，5，6。如果不是割点的点坍塌了，例如1，那么只要在2-7中任意设置一个即可。但如果是割点坍塌了，两边的人只能往两头跑，而我们看到，在上图中，只要设置两个点：一头一尾的逃生出口，就可以满足任何坍塌情况。

2.环

   如果在一个环上，每两个点都可以互相直达，那么我们可以设置任一个点作为逃生出口，即可满足其他所有点到达这个地方。但是要考虑逃生出口坍塌的情况，所以一个环上要设置两个逃生出口，可以使无论逃生出口是否坍塌，都有一个逃生出口可用。n个点中任选两个点，方案数是$ C^2_n =\frac{n(n-1)}{2}$

3.一般情况

   割点会分整个图为多个双连通分量，我们将每个双联通分量看作整个联通块，那么一个双连通分量中只需要设置一个点，就可以满足这个分量里的点能够跑到这个出口来。同上，我们还要考虑出口坍塌的情况。在这里，因为只会坍塌一个点，所以如果出口坍塌了，割点就不会坍塌，这个分量中的其他点可以通过割点跑到另外的双连通分量中，此时等价于同一个双连通分量。我们可以继续将这些点抽象为一个概念：叶子连通块。

4.叶子连通块

   叶子节点是没有出度的点，入度为1，也就是只连了一条边。那么叶子连通块的概念就是：只连接了一个割点的双连通分量。  同时，对于连接两个割点的双连通分量，其中一个割点坍塌，那么另一个割点就不会坍塌，可以通过另一个割点合并到另外一个双连通分量中。而叶子连通块就不行了，如果叶子连通块的割点（叶子的父亲）被切断，那么它就是一个单独的连通块，所以这里一定要设置一个逃生出口。在这里设置一个逃生出口，有weight种选择（weight是节点数）。根据乘法原理，最小个数是叶子连通块的个数；总方案数是所有叶子连通块的weight之积。

   所以我们只需要判断一个连通块dfs后是否只找到一个割点（用del数组存起来）

Code：

#include<iostream>
#include<cstring>
#include<cstdio>
using std::min;
using std::max;
using std::cin;
using std::cout;
struct node
{
    int n;
    node *nxt;
    node(int n)
    {
        this->n=n;
        nxt=NULL;
    }
    node()
    {
        nxt=NULL;
    }
};
node head[550],*tail[550];
int dfn[550],low[550],cnt=0;//tarjan核心数组
int n,m;
bool del[550];
void tarjan(int x,int from)//求割点数
{
    int son=0;
    dfn[x]=++cnt;
    low[x]=dfn[x];
    node *p=&head[x];
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(dfn[p->n])
            low[x]=min(low[x],dfn[p->n]);
        else
        {
            son++;
            tarjan(p->n,x);
            low[x]=min(low[x],low[p->n]);
            if(from!=0&&low[p->n]>=dfn[x])
                del[x]=true;//del=true就是割点
            if(from==0&&son>1)
                del[x]=true;
        }
    }
}
bool app[550];//是否出现过，判断一共有多少个点
unsigned long long sum=0;//sum<1<<64
int num=0,w=0;
bool used[550];
bool flag;
void dfs(int x)//判断是否为叶子连通块
{
    w++;//子节点个数
    node *p=&head[x];
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(used[p->n])//遍历过的点或出发割点
            continue;
        if(del[p->n])//找到另一个非出发割点的割点，说明不是叶子连通块
        {
            flag=true;
            continue;
        }
        used[p->n]=true;
        dfs(p->n);
    }
    return;
}

int main()
{
    int u,v,t=0;
    scanf("%d",&m);
    while(m!=0)
    {
        t++;
        cnt=0;
        n=0;
        num=0;
        sum=1;
        memset(app,0,sizeof(app));
        memset(del,0,sizeof(del));
        memset(dfn,0,sizeof(dfn));
        memset(used,0,sizeof(used));
        for(int i=1;i<=544;i++)//最多500个点
            tail[i]=&head[i];
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            app[u]=true;
            app[v]=true;
            if(u>n)
                n=u;
            if(v>n)
                n=v;
            tail[u]->nxt=new node(v);
            tail[u]=tail[u]->nxt;
            tail[v]->nxt=new node(u);
            tail[v]=tail[v]->nxt;
        }


        for(int i=1;i<=n;i++)
            if(!dfn[i])
                tarjan(i,0);

        for(int i=1;i<=n;i++)
            if(del[i]&&app[i])
            {
                used[i]=true;
                node *p=&head[i];
                while(p->nxt!=NULL)
                {
                    p=p->nxt;
                    if(!del[p->n]&&!used[p->n])
                    {
                        w=0;
                        used[p->n]=true;
                        flag=0;
                        dfs(p->n);
                        if(!flag)//乘法原理
                        {
                            num++;//联通块个数
                            sum*=w;//方案个数
                        }

                    }
                }
                used[i]=false;//
            }
        if(num==0)//如果没有割点
        {
            num=2;
            if(n-1==m)
                sum=2;
            else
                sum=n*(n-1)/2;//加法原理
        }
        printf("Case %d: %d ",t,num);
        cout<<sum<<std::endl;
        scanf("%d",&m);
    }
    return 0;
}

注：这个题给出的图应该是连通图，也就是一次能求完所有割点。不然如果一个矿场有两个矿区，比如两个不相交的环，就需要对每个环单独乘一次，这里没有考虑。