NKOJ 3985 (HNOI 2012) 矿场搭建（Tarjan求割点）

发表于 |
字数统计: 1,321字 | 阅读时长 ≈ 6min

P3985 [HNOI2012] 矿场搭建

问题描述

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

输入格式

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

输出格式

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

样例输入

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

样例输出

Case 1: 2 4
Case 2: 4 1

提示

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

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

此题容易想到割点，因为割点肯定不需要放出口，并且一个割点分出的分出联通块都需要放一个出口。
所以我们用Tarjan求出割点，把割点都删掉，再来求联通块。

观察发现，如果一个联通块和两个或以上的割点相连，这个联通块不需要放出口，那么我们在求联通块的时候顺便统计相连的割点数。
然后每一个需要放出口的联通块都只需要放一个即可，然后每一个点都可以放，有size种方案，然后乘法原理搞一下就行了。

但是仔细观察发现，一个联通块只需要放一个是有条件的，即他至少和一个割点相连，如果一个联通块不和任意一个割点相连，那么他需要放两个出口，这是容易证明的。因此有$C_{size}^{2}$种方案。

于是此题只需要求割点，再统计联通块相连的割点数和size即可。至于如何统计可以参考代码。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define M 1234
#define int long long
using namespace std;
int n,m,VT,T,scc,ans,cnt,tsize[M],size[M],dfn[M],low[M],be[M],cp[M],F[M];
int TOT,LA[M],EN[M],NE[M],V[M][M];
bool mark[M],mmark[M];
void Clear()
{
    TOT=1;ans=1;cnt=0;T++;
	scc=0;VT=0;n=0;
	memset(V,0,sizeof(V));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(be,0,sizeof(be));
	memset(cp,0,sizeof(cp));
    memset(LA,0,sizeof(LA));
    memset(F,0,sizeof(F));
    memset(mark,0,sizeof(mark));
    memset(mmark,0,sizeof(mmark));
    memset(size,0,sizeof(size));
    memset(tsize,0,sizeof(tsize));
}
void ADD(int x,int y)
{
    TOT++;
    EN[TOT]=y;
    NE[TOT]=LA[x];
    LA[x]=TOT;
}
void Tarjan(int u,int f)
{
    int i,v;
    dfn[u]=low[u]=++VT;
    for(i=LA[u];i;i=NE[i])
    {
        v=EN[i];
        if(!dfn[v])
        {
            Tarjan(v,u);
			tsize[u]++;
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]&&f!=0)mark[u]=1;
        }
        else if(v!=f)low[u]=min(low[u],dfn[v]);
    }
    if(f==0&&tsize[u]>1)mark[u]=1;
}
void FBE(int x)
{
    int i;
    if(mark[x])return;//是割点，不讨论
	size[scc]++;//统计size
	be[x]=scc;
    for(i=LA[x];i;i=NE[i])
    {
    	if(mark[EN[i]]&&F[EN[i]]!=scc)
    	{
    		F[EN[i]]=scc;//标记该割点已讨论
    		cp[scc]++;//统计相连的割点数
    		continue;
		}
    	if(!be[EN[i]])FBE(EN[i]);
	}
}
main()
{
    int i,x,y;
    scanf("%lld",&m);
    while(m)
    {
        Clear();
        for(i=1;i<=m;i++)
        {
            scanf("%lld%lld",&x,&y);
            if(V[x][y]||V[y][x])continue;
            V[x][y]=V[y][x]=1;//去重边
            ADD(x,y);ADD(y,x);
            if(n<x)n=x;
            if(n<y)n=y;
            mmark[x]=mmark[y]=1;//标记是否存在这个点
        }
        for(i=1;i<=n;i++)if(!dfn[i]&&mmark[i])Tarjan(i,0);//求割点
        for(i=1;i<=n;i++)if(!be[i]&&!mark[i]&&mmark[i])scc++,FBE(i);//找联通块
        for(i=1;i<=scc;i++)//计算答案，cnt表示出口数，ans表示方案数
		{
			if(cp[i]==0)cnt+=2,ans*=(size[i]*(size[i]-1)/2);
			else if(cp[i]<=1)cnt++,ans*=size[i];
		}
		printf("Case %lld: %lld %lld\n",T,cnt,ans);
		scanf("%lld",&m);
    }
}