uvalive_5135 Mining Your Own Business

题目:

  John Digger is the owner of a large illudium phosdex mine. The mine is made up of a series of tunnels that meet at various large junctions. Unlike some owners, Digger actually cares about the welfare of his workers and has a concern about the layout of the mine. Specifically, he worries that there may a junction which, in case of collapse, will cut off workers in one section of the mine from other workers (illudium phosdex, as you know, is highly unstable). To counter this, he wants to install special escape shafts from the junctions to the surface. He could install one escape shaft at each junction, but Digger doesn’t care about his workers that much. Instead, he wants to install the minimum number of escape shafts so that if any of the junctions collapses, all the workers who survive the junction collapse will have a path to the surface.
  Write a program to calculate the minimum number of escape shafts and the total number of ways in which this minimum number of escape shafts can be installed.

思路:

  先求出这个图中的点双联通分量,对应到原图上,每一个分量之间通过割点连接。如果删去一个割点,那么只有那些只有一个割点的分量会被独立出去,所以这种情况下最小的数量就是这样的分量个数。如果删去一个非割点,图的连通性不受影响,所以只要至少有 个就行。建求生井的位置只要是非割点都行。
  如果整个图只有一个分量,那么最小个数就是 ,方案数为 。如果有多个,那么最小个数就是只有一个割点的分量个数,方案数是

代码:

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i(a), i ##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i ##_END_(b); i >= i##_END_; i--)
#define mset(a, b) memset(a, b, sizeof a)
using namespace std;
typedef long long ll;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
const int N = 5e4 + 5;

template<int N, int M, class T> struct Link {
#define erep(k, G, o) for(int k = G.HEAD[o]; k; k = G.NXT[k])
    int HEAD[N], NXT[M], tot; T W[M];
    void clear() {tot = 0; mset(HEAD, 0);}
    void add(int x, T w) {NXT[++tot] = HEAD[x]; W[HEAD[x] = tot] = w;}
    T& operator[] (int x) {return W[x];}
};
Link<N, N * 2, int> G;

template<class T> 
inline void rd(T &a) {
    char c;
    bool f = false;
    for(c = getchar(); !isdigit(c); c = getchar()) f |= (c == '-');
    for(a = 0; isdigit(c); c = getchar()) a = (a << 1) + (a << 3) + c - '0';
    if(f) a = -a;
}

struct Edge {
    int u, v;
    bool operator!= (const Edge &e) const {
        return u != e.u || v != e.v;
    }
};
Edge stk[N];

int dfn[N], low[N], top, cur, bcnt, mark[N];
bool cut[N];
vector<int> vec[N];
void dfs(int o, int f) {
    int ch = 0;
    dfn[o] = low[o] = ++cur;
    erep(k, G, o) {
        int v = G[k];
        if(v == f) continue;
        if(!dfn[v]) {
            ch++;
            stk[++top] = (Edge) {o, v};
            dfs(v, o);
            tomin(low[o], low[v]);
            if(dfn[o] <= low[v]) {
                cut[o] = true;
                vec[++bcnt].clear();
                int tot = 0;
                do {
                    Edge e = stk[top];
                    if(mark[e.u] != bcnt) {
                        mark[e.u] = bcnt;
                        vec[bcnt].push_back(e.u);
                    }
                    if(mark[e.v] != bcnt) {
                        mark[e.v] = bcnt;
                        vec[bcnt].push_back(e.v);
                    }
                } while(stk[top--] != (Edge) {o, v});
            }
        }
        else if(dfn[v] < dfn[o]) {
            tomin(low[o], dfn[v]);
            stk[++top] = (Edge) {o, v};
        }
    }
    if(!f && ch == 1) cut[o] = 0;
}

int main() {
    int n, m;
    int cas = 0;
    while(scanf("%d", &m), m) {
        G.clear();
        n = 0;
        rep(i, 1, m) {
            int a, b;
            rd(a); rd(b);
            tomax(n, a);
            tomax(n, b);
            G.add(a, b); 
            G.add(b, a);
        }
        mset(dfn, 0); mset(cut, 0);
        mset(mark, 0);
        bcnt = cur = 0;
        rep(i, 1, n) 
            if(!dfn[i]) 
                dfs(i, 0);
        int ans1 = 0;
        ll ans2 = 1;
        if(bcnt == 1) {
            printf("Case %d: %d %lld\n", ++cas, 2, (ll) n * (n - 1) / 2);
            continue;
        }
        rep(i, 1, bcnt) {
            int tmp = 0;
            for(int v : vec[i])
                tmp += cut[v];
            if(tmp == 1) {
                ans1++;
                ans2 *= vec[i].size() - tmp;
            }
        }
        printf("Case %d: %d %lld\n", ++cas, ans1, ans2);
    }
    return 0;
}