洛谷 P3225 矿场搭建 —— tarjan + 点双分析

本文主要是介绍洛谷 P3225 矿场搭建 —— tarjan + 点双分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点我啊╭(╯^╰)╮

题目大意：

    无向图，任意一个矿点坍塌以后，其他所有矿点都必须有路到救援出口
    求最少设置几个救援出口，设置最少出口的方案数

解题思路：

    这道题确实有点难。。。

    对于一个点双联通分量，大小为 $K$ ，若没有割点与它相连
    说明它与世隔绝，则在这个联通分量里必须设置两个救援出口
    因为只设置一个点可能坍塌，方案数是 $C(k,2)$

    对于一个点双联通分量，若有一个割点与它相连
    只需要设置一个救援出口即可，因为即使这个点坍塌了，其他点也可以通过这个割点到其他分量里
    因此方案数是 $k$

    对于一个点双联通分量，若有 $\ge$ 两个割点与它相连
    则不需要设置出口，无论哪个割点坍塌了，都有另一个割点连通到外部
    因此方案数是 $0$

    那么会不会出现所有联通分量都有两个以上的割点与它相连呢？？
    显示是不存在的，聪明的孩子都知道。
    这样一看好像这题很简单，是错觉吗

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const int maxn = 505;
int n, m, cnt, cntc;
int dfn[maxn], low[maxn], vis[maxn];
int tot, color, iscut[maxn], cas;
ll ans1, ans2;
vector <int> g[maxn];void tarjan(int u, int fa){dfn[u] = low[u] = ++tot;int child = 0;for(auto v : g[u]){if(v == fa) continue;if(!dfn[v]) {child++;tarjan(v, u);low[u] = min(low[u], low[v]);if(low[v] >= dfn[u]) iscut[u] = 1;} else low[u] = min(low[u], dfn[v]);}if(!fa && child==1) iscut[u] = 0;
}void dfs(int u, int color){vis[u] = color, cnt++;for(auto v : g[u]){if(iscut[v] && color!=vis[v]) cntc++, vis[v] = color;if(!vis[v]) dfs(v, color);}
}signed main() {while(~scanf("%d", &m) && m){memset(dfn, 0, sizeof(dfn));memset(low, 0, sizeof(low));memset(vis, 0, sizeof(vis));memset(iscut, 0, sizeof(iscut));tot = color = ans1 = n = 0, ans2 = 1;for(int i=0; i<maxn; i++) g[i].clear();for(int i=1, u, v; i<=m; i++) {scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);n = max(n, max(u, v));}for(int i=1; i<=n; i++)if(!dfn[i]) tarjan(i, 0);for(int i=1; i<=n; i++){if(iscut[i] || vis[i]) continue;color++, cnt = cntc = 0;dfs(i, color);if(cntc == 0) ans1 += 2, ans2 *= cnt * (cnt - 1) / 2;else if(cntc == 1) ans1++, ans2 *= cnt;}printf("Case %d: %lld %lld\n", ++cas, ans1, ans2);}
}

这篇关于洛谷 P3225 矿场搭建 —— tarjan + 点双分析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---