P3225 [HNOI2012] 矿场搭建

雨点打透心脏的1/2处 2023-07-11 12:35 6阅读 0赞

## 题目描述 ##

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

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

## 输入格式 ##

输入文件有若干组数据，每组数据的第一行是一个正整数 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)。

一道题做了我6个小时。。。，完全不懂Tarjan，完全不知道啥是双连通分量啊，最要命的是一直不理解根据割点个数讨论的那个地方。。。查过来查过去，总算是搞清楚了。本来应该详细讲讲Tarjan的，但我实在是做吐了。。。就题讲题吧。

这是一道Tarjan求无向图中双连通分量的题。

1. 使用Tarjan找到割点，划分双连通分量。

2. 使用DFS搜索每个双连通分量，找到他们所连接的割点的数量。

3. 根据割点进行讨论。

大致思路：

1. 使用Tarjan算法找到所有的割点。因为Tarjan是基于深度优先搜索(DFS)的思想，所以Tarjan搜索完整个图之后，可以得到一棵树。下图中，图一是原图，图二是按照Tarjan搜素形成的一棵树。在这里，我们假设Tarjan递归的入口节点为黄色节点。

那么在Tarjan递归过程中，要判断一个点是否为割点，必须满足下面两个条件的其中一个。

<1> 如果当前节点是根节点，那么经过Tarjan递归形成的树中，它至少要有两个子节点(>=2)。

比如下图中的黄色节点，如果它有两个子节点的话，它就是一个割点。

对应代码：

PS：

有人可能会说：如果原图中两个W之间还有一条边，那么黄色节点不就不是割点了吗。

我回答：如果两个W之间有一条边，在进行Tarjan递归的时候，右边的W其实就成了左边W的子节点，而不会是黄色节点的子节点。黄色节点其实还是只有一个子节点。如图三所示。

<2>如果当前节点U在树中是非根节点，如果它的子节点V在原图中不能有通向U的父节点或者祖宗节点的路径，比如，图中的红色线段，如果没有这根红色线段的话，U就是一个割点（或者W是割点），但是如果有这条指向边，那么U就不是割点。

对应代码：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE1Njg2_size_16_color_FFFFFF_t_70][]

图一 原图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE1Njg2_size_16_color_FFFFFF_t_70 1][]

图二 Tarjan形成的树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE1Njg2_size_16_color_FFFFFF_t_70 2][]

图三 若原图两个W之间有一条边，经过Tarjan形成的树。

题目思路：

图中红色为割点G1、G2，浅蓝色为出口O1、O2。

蓝色区域、黄色区域（加上O1）、绿色区域（加上O2）分别是三个双连通分量。

1. 如果双连通分量连接着一个割点。比如下图中的双连通分量1和双连通分量3。那么他们必须在其中选择一个点作为出口。

情况一：O1(或O2)坍塌，那么所有的点都可以从O2(或O1)出去

情况二：G1坍塌，那么A区域可以从O1出去，B、C区域可以从O2出去。

情况三：G2坍塌，那么C区域可以从O2出去，B、C区域可以从O1出去。

总之，如果双连通分量连接着一个割点，那么必须选择其中一个点作为出口。

2. 如果双连通分量连接着两个割点。比如下图中的双连通分量2。那么这个双连通分量中不需要设置出口。

情况一：G1坍塌，那么B区域的点可以通过G2到达O2。

情况二：G2坍塌，那么B区域的点可以通过G1到达O1。

总之，总会有一个割点不会坍塌，使得B区域的点可以通过这个割点，到达某个双连通分量的出口。

但是如果双连通分量只连接一个割点，如果这个割点出发，它就被孤立了，所以必须在其中设置一个出口。

3. 如果双连通分量没有连接割点，比如下面第二个图，那么它必须在其中设置两个出口，这样其中一个坍塌之后，可以通过另一个出口出去。

（哇，写的好累。。。）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE1Njg2_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE1Njg2_size_16_color_FFFFFF_t_70 4][]

#include<iostream>
    #include<algorithm>
    #include<string>
    #include<vector>
    #include<queue>
    #include<stack>
    #include<map>
    #include<unordered_map>
    #include<set>
    #include<sstream>
    using namespace std;
    const int MAXN = 505; 
    
    vector<int> adj[MAXN];
    long long t,n;
    long long u,v;
    long long cnt = 1;
    /*
    ** low数组，假设low[v] = 5;
    ** 说明从v节点出发，能到达第五次Tarjan递归时的点，
    ** 假设第五次是对w节点进行的递归，也就说明v节点能够达到w节点。 
    ** 注意点：并不是说v只能到达w，可能w还能到达z节点，
    ** 也就是说v其实也能到达z节点。 
    */
    int low[MAXN];  //Low[u]为u或u的子树能够追溯到的最早的Tarjan次序号。 
    int dfn[MAXN];  //初始值都为0，表示还未访问，即：还未递归。 
    int cut[MAXN];  //cut[u]=true 表示u是割点。 
    long long index;  //记录当前Tarjan递归的次数。（不是层数，是次数） 
    long long root;  //记录Tarjan的入口节点，也就是根节点。 
    long long childNum;   //根节点对应的子节点的数量 
    void Tarjan(int u,int parent){
    	dfn[u] = low[u] = ++index;
    	for(int i=0;i<adj[u].size();i++){
    		int v = adj[u][i];
    		if(!dfn[v]){   //如果v节点还没有访问过 
    			Tarjan(v,u);
    			low[u] = min(low[u],low[v]); 
    			//判断割点啦 
    			//满足第二个条件，v没有通向u父亲节点或祖宗节点的路线。
    			//此时u一旦去除，v以及v的子节点就孤立了，所以u是割点。 
    			if(low[v] >= dfn[u]){ 
    				//满足第一个条件，u是根节点 
    				if(u == root){
    					childNum++; 
    					//如果子节点已经大于等于两个了，它就是割点。 
    					if(childNum>=2){
    						cut[u] = true;
    					}
    				}else{
    					cut[u] = true;
    				} 
    			}
    		}else if(v != parent){
    			low[u] = min(low[u],dfn[v]);
    		}
    	}
    }
    
    int vis[MAXN]; //vis[u] = 1  表示u节点属于第一个双连通分量 
    long long cutNum;  //当前双连通分量连接着的割点数 
    long long totalNum; //当前双连通分量共有多少个点（割点除外） 
    long long out; //总共需要设置多少个出口。 
    long long plan; //有多少种方案 
    long long group; 
    /*
    ** 查看当前的双连通分量连接着几个割点。
    ** 割点会把原来的连通分量划分为
    ** 若干个双连通分量，我们就是要看看
    ** 每一个双连通分量在原来的连通分量中
    ** 连接着几个割点。 
    */
    void DFS(int u){
    	vis[u] = group;
    	totalNum++; 
    	for(int i=0;i<adj[u].size();i++){
    		int v = adj[u][i];
    		/*
    		**u是割点并且没有被这个双连通分量访问过，
    		**因为一个割点可能连接多个双连通分量 
    		**/ 
    		if(cut[v] && vis[v]!=group){ 
    			cutNum++; //双连通分量的割点+1 
    			vis[v] = group;
    		}
    		if(!vis[v]){ //如果不是割点并且没有没访问过 
    			DFS(v);
    		}
    	} 
    }
    
    void DFSTravel(){
    	for(int i=1;i<=n;i++){
    		if(!vis[i] && !cut[i]){ //不能是已访问过的点，也不能是割点 
    			cutNum = 0;  //重置cutNum的值。 
    			totalNum = 0;  
    			group++;
    			DFS(i);
    			if(cutNum == 0){ 
    				out += 2;
    				plan *= totalNum*(totalNum-1)/2;
    			}else if(cutNum == 1){
    				out++;
    				plan *= totalNum;
    			}
    			//如果cutNum==2，不用设置出口。 
    		}
    	}
    }
    
    void TarjanTravel(){
    	for(int i=1;i<=n;i++){
    		if(!dfn[i]){
    			childNum = 0; //重置子节点数量的值。 
    			root = i; 
    			Tarjan(i,i);
    		}
    	}
    }
    
    void init_data(){
    	//设置初值 
    	fill(cut,cut+n+1,false);
    	fill(dfn,dfn+n+1,0);
    	fill(vis,vis+n+1,0);
    	index = 0;
    	plan = 1; 
    	out = 0; 
    	group = 0; //当前双连通分量的序号 
    }
    
    void destroy(){
    	for(int i=1;i<MAXN;i++){
    		adj[i].clear();
    	}
    	n = 0;
    }
    
    int main(){
    	while(cin>>t && t!=0){
    		for(int i=0;i<t;i++){
    			cin>>u>>v;
    			adj[u].push_back(v);
    			adj[v].push_back(u);
    			n = max(n,max(u,v));
    		}
    		init_data();
    		TarjanTravel();
    		DFSTravel(); 
    		destroy();
    		cout<<"Case "<<cnt<<": "<<out<<" "<<plan<<endl; 
    		cnt++;
    	}
    	return 0; 
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE1Njg2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020030516554223.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE1Njg2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE1Njg2_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200305164513790.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE1Njg2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE1Njg2_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020030516522072.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE1Njg2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE1Njg2_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200305173701711.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE1Njg2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE1Njg2_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200305174955709.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE1Njg2,size_16,color_FFFFFF,t_70