LuoguP3225[HNOI2012]矿场搭建

Sundial · 2019-11-02 09:13:29 · 题解

[题目传送门]

思路的话其他大佬都已经讲的很清楚了qwq 我主要是想再提供一种写法

其实是自己太菜看不懂其他巨佬的代码QAQ

代码里也有一些解释，主要就是要会点双联通分量(代码里的 点分 )就好了

献上蒟蒻的代码 Code:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e4 + 7;
int n, m;
int tot, head[N];
bool cut[N];//记录一个点是不是割点 
vector<int> dcc[N];//记录每个点双里面点 
int id, top, vdcc, dfn[N], low[N], stk[N];
struct edge{
    int net, to;
}e[N * 3];
void add(int u, int v) {
    e[++tot] = {head[u], v};
    head[u] = tot;
}
void tarjan(int u, int fa) {//求点分模板 
    dfn[u] = low[u] = ++id;
    stk[++top] = u;
    if (u == fa && !head[u]) {//单独的点就计入单独的点分 
        dcc[++vdcc].push_back(u);
        return;
    }
    int flag = 0;
    for (int i = head[u]; i; i = e[i].net) {
        int to = e[i].to;
        if (!dfn[to]) {
            tarjan(to, u);
            low[u] = min(low[u], low[to]);
            if (low[to] >= dfn[u]) {
                flag++;
                if (u != fa || flag > 1) {
                    cut[u] = true;//记下割点 
                }
                vdcc++;
                dcc[vdcc].clear();//多组数据要清空 
                int y;
                do {
                    y = stk[top--];
                    dcc[vdcc].push_back(y);
                } while (y != to);//注意这里是to 
                dcc[vdcc].push_back(u);
            }
        } else {
            low[u] = min(low[u], dfn[to]);
        }
    }
}
int main () {
    int Case = 0;
    while (scanf("%d", &m) && m != 0) {
        Case++;
        ll ans1 = 0, ans2 = 1; 
        vdcc = tot = top = id = 0;
        memset(head, 0, sizeof head);
        memset(cut, 0, sizeof cut);
        memset(dfn, 0, sizeof dfn);
        //注意一下多组数据的清空,low数组会被id更新,不用清 
        n = 0;
        for(int i = 1; i <= m; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            add(u, v), add(v, u);
            n = max(n, max(u, v));//题里面没说点标号就只好自己取max 
        }
        for (int i = 1; i <= n; i++) {
            if (!dfn[i]) {
                tarjan(i, i);
            }
        }
        for (int i = 1; i <= vdcc; i++) {
            int cutnum = 0;
            int siz = (int)dcc[i].size();
            for (int j = 0; j < siz; j++) {
                if (cut[dcc[i][j]]) {
                    cutnum++;//记录该点分之中的割点数 
                }
            }
            if (siz == 1) {//单独的点特判一下 
                ans1++;
                continue;
            }
            if (cutnum == 1) {
                ans1++;
                ans2 *=(siz - 1);
                //如果只有一个割点的话,必须要再建一个非割点的出口
                //这样才能保证在割点坍塌之后该点分还能出去 
            } else if (!cutnum) {
                ans1 += 2;
                ans2 *= siz * (siz - 1) / 2;
                //如果没有割点的话就必须建两个出口,然后就是C(n,2),化简后就是n*(n-1)/2
            }
            //还有一种情况就是有两个割点
            //此时无论哪个点塌了,该点分里的点都能有地方出去,所以不需要建出口了 
        }
        printf("Case %d: %lld %lld\n", Case, ans1,ans2);
    }
    return 0;
}

蒟蒻也是才开始看双联通分量，如果有不妥的地方还请巨佬们指出

感谢观赏