c3pool网页挖矿_actin

c3pool网页挖矿_actin煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。请写一个程序,用来计算至少需要设置几个救援出口,以及不同最少救援出口的设置方案总数。输入格式输入文件有若干组数据,每组数据的第一行是一个正整数 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/168615.html原文链接:https://javaforall.cn

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

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

(0)


相关推荐

  • matlab模糊控制工具箱使用教程_模糊pid控制原理

    matlab模糊控制工具箱使用教程_模糊pid控制原理Matlab模糊控制工具箱为模糊控制器的设计提供了一种非常便捷的途径,通过它我们不需要进行复杂的模糊化、模糊推理及反模糊化运算,只需要设定相应参数,就可以很快得到我们所需要的控制器,而且修改也非常方便。下面将根据模糊控制器设计步骤,一步步利用Matlab工具箱设计模糊控制器。1、模糊控制工具箱使用首先我们在Matlab的命令窗口(commandwindow)中输入fuzzy,回车就会出来…

  • 数据库常见查询语句_数据库检索语句

    数据库常见查询语句_数据库检索语句常用数据库查询语句基本查询select字段1,字段2,…from表名;例如:selectid,namefromstu;条件查询select字段1,字段2,…from表名where字段关系符号值;关系符号<=>=<=!=大于等于大于等于小于等于不等于例如:select*fromstuid>2;andorin(范围内满足in内部条件)

  • Java 实现MD5加密「建议收藏」

    Java 实现MD5加密「建议收藏」Java实现MD5加密

  • Docker Compose搭建mycat读写分离

    Docker Compose搭建mycat读写分离接上篇docker-compose部署mysql主从复制,本文介绍如何搭建mycat中间件,并用mycat来做读写分离.配置文件以及文档地址:mycat-rw系统环境docker1.12.3mysql5.7.17deepin15.3桌面版(这个没啥影响,因为我们用docker)mycat1.6要点说明看上篇文章的详细介绍暴露mysqlmycat端口号,方便管理本文直接从dock

    2022年10月10日
  • 如何挑选黑莓手机

    如何挑选黑莓手机

  • c++写windows窗口程序_windows7硬件配置要求

    c++写windows窗口程序_windows7硬件配置要求原文转载:http://blog.csdn.net/da_keng/article/details/50589145纯属转载,复制过来方便编程时寻找。感谢作者:I-Awakening复制前补充:在刚学C#,用ManagementObjectSearcher竟然不能解析到头文件,需要手动AddReferance..前言:我们在很多情况下想要获得计算机的…

发表回复

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

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