题解 UVA1108 【Mining Your Own Business】

## 附原题描述： 有一座地下的稀有金属矿由n条隧道和一些连接点组成，其中每条隧道连接两个连接点。任意两个连接点之间最多只有一条隧道。为了降低矿工的危险，你的任务是在一些连接点处安装太平井和相应的逃生装置，使得不管哪个连接点倒塌，不在此连接点的所有矿工都能到达太平井逃生（假定除倒塌的连接点不能通行外，其他隧道和连接点完好无损）。为了节约成本，你应当在尽量少的连接点安装太平井。你还需要计算出在太平井的数目最小时的安装方案总数。 ### 输入数据 输入包含多组数据。每组数据第一行为隧道的条数n(n<=50000),一下n行，每行两个整数，即一条隧道两段的连接点的编号(所有连接点从1开始编号)。每组数据的所有连接点保证连通。 输入以数字0作为结束 ### 输出数据 对于每组数据，输出两个整数，即最少需要安装的太平井数目以及对应的方案总数。 答案保证在64位带符号整数范围以内。 ------------ ------------ ## 题解部分 这道题很明显先要求出各个点双连通分量。但求出了双连通分量又怎么做呢？ 求出各个双连通分量的割点。 如果一个双连通分量内有多个割点，就不用安装太平井，因为在这个双连通分量内的点都可以通过割点到达其他连通分量内的太平井 如果只有一个割点，那么在割点坍塌就没有办法到达其他连通分量了，所以需要安装一个太平井，方案数就是连通分量的点数减一 如果整个图都是一个连通分量，那么需要建两个太平井，一个塌了，另一个还能用，若顶点数为n，方案数就是n(n-1)/2 注意，各个连通分量的方案数，根据乘法原理应当乘起来 最后，代码如下： ```cpp #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int s[100000]; int n,m,cnt=0,tot=0,num=0,p=0; int head[101000],nxt[101000],to[101000]; int low[100010],pre[101000],f[101000],l[100100]; int re[101010]; vector <int> vec[100000]; void addedge(int x,int y) { cnt++; nxt[cnt]=head[x]; head[x]=cnt; to[cnt]=y; } void dfs(int u,int fa) { low[u]=pre[u]=++tot; s[++p]=u; for(int i=head[u];i!=-1;i=nxt[i]) { int v=to[i]; if(!pre[v]) { dfs(v,u); low[u]=min(low[u],low[v]); if(low[v]>=pre[u]) { num++; vec[num].clear(); while(p) { vec[num].push_back(s[p]); l[s[p]]++; if(s[p]==v) break; p--; } vec[num].push_back(u); p--; l[u]++; } } else if(pre[v]<pre[u] && v!=fa) low[u]=min(low[u],pre[v]); } } void Slove() { long long ans1=0,ans2=1; for(int i=1;i<=num;i++) { int res=0; if(vec[i].size()==1 && l[vec[i][0]]>1) continue; for(int j=0;j<vec[i].size();j++) if(l[vec[i][j]]>1) res++; //统计割顶个数 if(res==1) ans1++,ans2*=(long long)vec[i].size()-1; } if(num==1) ans1=2,ans2=(long long)vec[1].size()*(vec[1].size()-1)/2;//整个图都为一个连通分量需要特判 printf("%lld %lld\n",ans1,ans2); } int main() { int T=0; while(1) { T++; memset(f,0,sizeof(f)); memset(l,0,sizeof(l)); memset(re,0,sizeof(re)); memset(pre,0,sizeof(pre)); memset(low,0,sizeof(low)); memset(head,-1,sizeof(head)); n=0,cnt=0,tot=0,num=0,p=0; scanf("%d",&m); if(!m) break; for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); if(!re[x]) re[x]=++n;//因为题目并没有告诉点的数量，所以做了离散化 if(!re[y]) re[y]=++n; addedge(re[x],re[y]); addedge(re[y],re[x]); } for(int i=1;i<=n;i++) if(!pre[i]) dfs(i,0);//tarjan求出连通分量和割顶 printf("Case %d: ",T); Slove(); } return 0; } ```