C/C++知识点之实战-矿场搭建 (点双连通)
从安 2019-06-05 来源 : 阅读 889 评论 0

摘要:本篇文章主要讲述C/C++知识点之实战-矿场搭建 (点双连通),希望阅读本篇文章以后大家有所收获,帮助大家对相关内容的理解更加深入。

本篇文章主要讲述C/C++知识点之实战-矿场搭建 (点双连通),希望阅读本篇文章以后大家有所收获,帮助大家对相关内容的理解更加深入。

C/C++知识点之实战-矿场搭建 (点双连通)

题目

矿场搭建

解析

1. 连通块中一个割点也没有,这时我们至少要建两个出口,以防万一某个出口塌了,方案的话就从size(联通块大小)个点中随便选两个,也是(size2)(size2)个。

2. 联通块中有一个割点,如果这个割点塌了,需要一个出口,但如果塌的不是割点,我们可以通过割点跑到另一个连通块中,所以只需要割点。根据乘法原理,方案数只需要乘上这个连通块的size。

3. 联通块中大于两个割点的时候,若一个割点塌了,可以通过另一个割点跑到另一个联通块里,所以不需要再加出口。

需要注意的是
题目中没有给出具体多少个点,但应该是连续的,因为我按连续的做的

代码

#include #define int long longusing namespace std;const int N = 1e6 + 10;int n, m, js, cnt, num, sum, size, tot, ans1, ans2;/*  js计数器
    sum联通块编号
    tot联通块中割点个数
    size联通块中点的个数
    ans1第一问答案
    ans2第二问答案
*/int head[N], dfn[N], low[N], bel[N];bool cut[N], vis[N];class node {
    public :
        int v, nx;
} e[N];
templateinline void read(T &x) {
    x = 0; int f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    x = f ? -x : x;
    return;
}
inline void add(int u, int v) {
    e[++num].nx = head[u], e[num].v = v, head[u] = num;
}
void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++cnt;
    int child = 0;
    for (int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if (!dfn[v]) {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u] && u != fa) cut[u] = 1, vis[u] = 1;
            if (u == fa) child++;
        }
        low[u] = min(low[u], dfn[v]);
    }
    if (child >= 2 && u == fa) cut[u] = 1, vis[u] = 1;
}
void dfs(int u) {
    vis[u] = 1;
    size++;
    for (int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if (!vis[v] && !cut[v]) dfs(v);     //没有被访问过且不是割点
        if (cut[v] && bel[v] != sum) bel[v] = sum, tot++;   //用来标记割点在哪个连通块内
    }
}
signed main() {
    while (scanf("%lld", &n) && n) {
        num = cnt = m = ans1 = 0;
        ans2 = 1;
        memset(e, 0, sizeof (e));
        memset(dfn, 0, sizeof (dfn));
        memset(low, 0, sizeof (low));
        memset(cut, 0, sizeof (cut));
        memset(vis, 0, sizeof (vis));
        memset(bel, 0, sizeof (bel));
        memset(head, -1, sizeof (head));
        for (int i = 1, x, y; i <= n; ++i) {
            read(x), read(y);
            add(x, y), add(y, x);
            m = max(m, max(x, y));
        }
        for (int i = 1; i <= m; ++i) if (!dfn[i]) tarjan(i, i);
        for (int i = 1; i > 1;
            if (tot == 1) ans1++, ans2 *= size;
        }
        printf("Case %lld: %lld %lld\n", ++js, ans1, ans2);
    }
}

 

本文由职坐标整理发布,学习更多的相关知识,请关注职坐标IT知识库!

本文由 @从安 发布于职坐标。未经许可,禁止转载。
喜欢 | 0 不喜欢 | 0
看完这篇文章有何感觉?已经有0人表态,0%的人喜欢 快给朋友分享吧~
评论(0)
后参与评论

您输入的评论内容中包含违禁敏感词

我知道了

助您圆梦职场 匹配合适岗位
验证码手机号,获得海同独家IT培训资料
选择就业方向:
人工智能物联网
大数据开发/分析
人工智能Python
Java全栈开发
WEB前端+H5

请输入正确的手机号码

请输入正确的验证码

获取验证码

您今天的短信下发次数太多了,明天再试试吧!

提交

我们会在第一时间安排职业规划师联系您!

您也可以联系我们的职业规划师咨询:

小职老师的微信号:z_zhizuobiao
小职老师的微信号:z_zhizuobiao

版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
 沪公网安备 31011502005948号    

©2015 www.zhizuobiao.com All Rights Reserved

208小时内训课程