acwing-396. 矿场搭建(Tarjan点双连通分量)「建议收藏」

acwing-396. 矿场搭建(Tarjan点双连通分量)「建议收藏」煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。请写一个程序,用来计算至少需要设置几个救援出口,以及不同最少救援出口的设置方案总数。输入格式输入文件有若干组数据,每组数据的第一行是一个正整数 N,表示工地的隧道数。接下来的 N 行每行是用空格隔开的两个整数 S 和 T,表示挖煤点 S 与挖煤点 T 由隧道直接连

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。

为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。

于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。

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

输入格式
输入文件有若干组数据,每组数据的第一行是一个正整数 N,表示工地的隧道数。

接下来的 N 行每行是用空格隔开的两个整数 S 和 T,表示挖煤点 S 与挖煤点 T 由隧道直接连接。

注意,每组数据的挖煤点的编号为 1∼Max,其中 Max 表示由隧道连接的挖煤点中,编号最大的挖煤点的编号,可能存在没有被隧道连接的挖煤点。

输入数据以 0 结尾。

输出格式
每组数据输出结果占一行。

其中第 i 行以 Case i: 开始(注意大小写,Case 与 i 之间有空格,i 与 : 之间无空格,: 之后有空格)。

其后是用空格隔开的两个正整数,第一个正整数表示对于第 i 组输入数据至少需要设置几个救援出口,第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总数。

输入数据保证答案小于 264,输出格式参照以下输入输出样例。

数据范围
1≤N≤500,
1≤Max≤1000

输入样例:
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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
const int M = 1e3 + 10;
typedef unsigned long long ULL;
struct Edge{ 

int v,next;
}edge[M];
int head[N],cnt;
void add(int u,int v){ 

edge[cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt ++;
}
int in[N];
int sccno;
vector<int>g[N];
int low[N],num[N],dfn;
int sta[N],top;
int is_solate[N],cut[N];
//点双连通分量
void Tarjan(int u,int fa){ 

num[u] = low[u] =  ++dfn;
if(fa == -1 && head[u] == -1){ 
      //孤立节点特判
sccno ++;
g[sccno].push_back(u);
is_solate[sccno] = true;
return;
}
sta[top ++] = u;
int child = 0;
for(int i = head[u];~i;i = edge[i].next){ 

int v = edge[i].v;
if(v == fa)continue;
if(!num[v]){ 

child ++;
Tarjan(v,u);
low[u] = min(low[u],low[v]);
if(low[v] >= num[u]){ 

if(fa != -1)cut[u] = true;
int t;
sccno ++;
while(true){ 

t = sta[-- top];
g[sccno].push_back(t);
if(t == v)break;
}
g[sccno].push_back(u);
}
}
else low[u] = min(low[u],num[v]);
}
if(fa == -1 && child >= 2)cut[u] = true;
}
int main(){ 

int m = 0;
int x,y;
int n;
int T = 0;
while(cin>>m,m){ 

n = 0;
memset(head,-1,sizeof head);
memset(num,0,sizeof num);
memset(low,0,sizeof low);
memset(cut,0,sizeof cut);
dfn = 0,cnt = 0;
for(int i = 1;i <= sccno;i ++)g[i].clear();
sccno = 0;
for(int i = 0;i < m;i ++){ 

cin>>x>>y;
add(x,y),add(y,x);
n = max(n,max(x,y));
}
for(int i = 1;i <= n;i ++){ 

if(!num[i])Tarjan(i,-1);
}
ULL res = 0;
ULL c = 1;
for(int i = 1;i <= sccno;i ++){ 

int d = 0;
for(auto &a : g[i]){ 

if(cut[a])d ++;
}
int a = g[i].size() - d;
if(d == 0){ 

if(a == 1)res += 1;
else res += 2,c *= (a * (a - 1) / 2);
}
else if(d == 1){ 

if(a == 1)res += 1;
else res += 1,c *= a;
}
}
printf("Case %lld: %lld %lld\n",++T,res,c);
}
return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169108.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 中文停用词_中文停用词哪个

    中文停用词_中文停用词哪个!"#$%&'()*+,…………………………../.一.数.日///0123456789:://::;<=>>&g

  • drupal安装配置错误

    drupal安装配置错误安装配置错误#########################################################################1、403错误 查看errorlog发现:AH01630:clientdeniedbyserverconfiguration:F:/phpweb/drupal——————————-…

  • 怎么让FOXMAIL关了以后在右下角自动收取邮件

    怎么让FOXMAIL关了以后在右下角自动收取邮件

    2021年10月19日
  • cmd命令切换盘符_cmd更改盘符名

    cmd命令切换盘符_cmd更改盘符名cd/dD:\Test\切换到D盘Test文件夹下dir查看文件夹内容cd是用来进入目录,或退出目录的CD\是回到根目录CD..是回到上级目录cd子目录名,进入下级目录CD绝对路径,进入你的绝对路径的目录里如可以在C:\WINDOWS\SYSTEM32下输入cdd:\program\firefox\来进入d:\program\firefox目录里

  • x201换风扇_笔记本怎么换风扇 ThinkPad X201i换风扇图文教程

    x201换风扇_笔记本怎么换风扇 ThinkPad X201i换风扇图文教程ThinkPadX201i换电扇图文教程:拆机之前,我们需求先对X201i的散热电扇在停止了开端的理解,得知价钱从10元左右的单电扇,到上百的散热全体都有,而且还分东芝产和松下产等不同产地的,小编选择了松下产的整套散热(包括散热片和电扇),价钱为150,电扇固定办法为小螺丝。假定拿到电脑修理店去换的话,小编猜测我们所需求的费用至少在200-300元之间。一:拆机前的准备螺丝刀,小毛刷和安排螺丝的…

  • db4o 参考资料

    db4o 参考资料转自IBM:http://www.ibm.com/developerworks/cn/java/jdb4o/本系列是对开放源码数据库db4o的详尽介绍,db4o可以充分利用当前的面向对象的语言、系统和理念。要下载db4o,可以参考db4o主页;为了实践本系列的示例,需要下载db4o。系列文章第1部分:简介和概览(2007年4月9日)

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号