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)


相关推荐

  • imx8主频_5g网络和处理器有关系吗

    imx8主频_5g网络和处理器有关系吗ByToradex秦海1).简介NXPiMX8已经正式发布,相较于之前NXPi.MX系列的主力产品iMX6,其性能有了大幅提升,本文就针对网络接口对NXPiMX8和iMX6两款ARM处理器进行对比测试。本文演示所使用的ARM平台来自Toradex基于NXPiMX8SoC的ApalisiMX8ARM核心板和基于NXPiMX6QSoC的ApalisiMX6…

    2022年10月21日
  • css+div网页设计(一)–基础知识

    css+div网页设计(一)–基础知识

    2021年12月10日
  • 惠普台式电脑如何安装系统_hp服务器快速重装系统

    惠普台式电脑如何安装系统_hp服务器快速重装系统惠普在计算机行业是一个很有声誉的品牌,无论是台式机还是笔记本,惠普都是一款值得考虑和购买的品牌产品之一。但是当计算机系统出了问题需要重装系统时,很多人并不知道如何进行系统的重装,那么惠普的台式机如何进行重装系统呢?今天小编将为大家介绍惠普台式电脑装系统步骤。惠普台式电脑装系统步骤阅读1、打开浏览器搜索云骑士官网,找到云骑士官网并点击打开。2、在官网下载云骑士一键重装系统软件,下载后打开云骑士装机大…

  • 中星睿典职称计算机考试,大纲教材 – 中星睿典 – 全国职称计算机考试|职称计算机考试模块|全国职称计算机考试试题…

    中星睿典职称计算机考试,大纲教材 – 中星睿典 – 全国职称计算机考试|职称计算机考试模块|全国职称计算机考试试题…大纲教材介绍全国专业技术人员计算机应用能力考试,又称全国职称计算机应用考试。为贯彻党的十五届五中全会提出的“要在全社会广泛应用信息技术,全国职称计算机考试可以提高计算机和网络的普及应用程度,加强信息资源的开发和利用”的精神,落实国家加快信息化建设的要求,引导全国专业技术人员学习掌握计算机知识,提高计算机的应用能力,根据原人事部《关于全国专业技术人员计算机应用能力考试的通知》(人发2001124号)…

  • J2ME开发资料[通俗易懂]

    J2ME开发资料[通俗易懂]分享一个实用的网络连接类:http://www.cnblogs.com/psunny/archive/2009/12/06/1617875.html一些知名的J2me优秀开源UI项目: http://www.cnblogs.com/psunny/archive/2009/09/23/1572740.html最佳的线程联网类:http://www.cnblogs.com/psunny/arch

  • csdn操作文档[通俗易懂]

    csdn操作文档[通俗易懂]csdn操作文档

发表回复

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

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