https://www.luogu.org/problemnew/show/P3225?

題意

煤礦工地可以看成是由隧道連接挖煤點組成的無向圖。為安全起見，希望在工地發生事故時所有挖煤點的工人都能有一條出路逃到救援出口處。于是礦主決定在某些挖煤點設立救援出口，使得無論哪一個挖煤點坍塌之后，其他挖煤點的工人都有一條道路通向救援出口。

請寫一個程序，用來計算至少需要設置幾個救援出口，以及不同最少救援出口的設置方案總數。

思路

找出圖中的割點，利用tarjan， 然后對非割點的聯通塊dfs。

找出一個塊中直接相鄰的割點個數。
如果個數為0，說明不能通過割點出逃，所以要在這個聯通塊中選兩個點作為出口。
如果個數為1，要另找一個出口，以防割點被堵住。
如果個數>=2, 就不用了，從割點出逃就行了。

?

#include <algorithm> #include <iterator> #include <iostream> #include <cstring> #include <cstdlib> #include <iomanip> #include <bitset> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <stack> #include <cmath> #include <queue> #include <list> #include <map> #include <set> #include <cassert>/*?_ヽ＼＼ Λ＿Λ 來了老弟＼('?')>　⌒ヽ/ 　 へ＼/　　/　＼＼ﾚ　ノ　　 ヽ_つ/　//　/|(　(ヽ|　|、＼| 丿 ＼ ⌒)| |　　) / 'ノ )　　Lﾉ*/using namespace std; #define lson (l , mid , rt << 1) #define rson (mid + 1 , r , rt << 1 | 1) #define debug(x) cerr << #x << " = " << x << "\n"; #define pb push_back #define pq priority_queuetypedef long long ll; typedef unsigned long long ull; //typedef __int128 bll; typedef pair<ll ,ll > pll; typedef pair<int ,int > pii; typedef pair<int,pii> p3;//priority_queue<int> q;//這是一個大根堆q //priority_queue<int,vector<int>,greater<int> >q;//這是一個小根堆q #define fi first #define se second //#define endl '\n'#define boost ios::sync_with_stdio(false);cin.tie(0) #define rep(a, b, c) for(int a = (b); a <= (c); ++ a) #define max3(a,b,c) max(max(a,b), c); #define min3(a,b,c) min(min(a,b), c);const ll oo = 1ll<<17; const ll mos = 0x7FFFFFFF; //2147483647 const ll nmos = 0x80000000; //-2147483648 const int inf = 0x3f3f3f3f; const ll inff = 0x3f3f3f3f3f3f3f3f; //18 const int mod = 1e9+7; const double esp = 1e-8; const double PI=acos(-1.0); const double PHI=0.61803399; //黃金分割點 const double tPHI=0.38196601;template<typename T> inline T read(T&x){x=0;int f=0;char ch=getchar();while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x=f?-x:x; }inline void cmax(int &x,int y){if(x<y)x=y;} inline void cmax(ll &x,ll y){if(x<y)x=y;} inline void cmin(int &x,int y){if(x>y)x=y;} inline void cmin(ll &x,ll y){if(x>y)x=y;}/*-----------------------showtime----------------------*/const int maxn = 509;struct E{int v,nxt;}edge[maxn*maxn];int head[maxn],gtot=0;void addedge(int u,int v){edge[gtot].v = v;edge[gtot].nxt = head[u];head[u] = gtot++;}int dfn[maxn],low[maxn],cnt = 0;int cut[maxn];int rt,rs;void tarjan(int u,int fa){dfn[u] = low[u] = ++cnt;for(int i=head[u]; ~i; i = edge[i].nxt){int v = edge[i].v;if(!dfn[v]){tarjan(v,u);low[u] = min(low[u], low[v]);if(low[v] >= dfn[u]){if(u == rt) {rs++;}else cut[u] = 1;}}else if(v != fa){low[u] = min(low[u], dfn[v]);}}}int vis[maxn],mark = 0;int num,ge_num;void dfs(int u){vis[u] = mark;num++;for(int i=head[u]; ~i; i = edge[i].nxt){int v = edge[i].v;if(cut[v] && vis[v] < mark){vis[v] = mark;ge_num++;}else if(!vis[v]){dfs(v);}}} int main(){int m,n,cas=0;while(~scanf("%d", &m) && m) {memset(head, -1, sizeof(head));gtot = 0;cnt=0;n = 0;for(int i=1; i<=m; i++) {int x,y; scanf("%d%d", &x, &y);addedge(x, y);addedge(y, x);n = max(n, x);n = max(n, y); }memset(dfn, 0, sizeof(dfn));memset(low, 0 ,sizeof(low));memset(cut, 0, sizeof(cut));for(int i=1; i<=n; i++) {if(dfn[i] == 0) {rt = i;rs = 0;tarjan(i, -1);if(rs >= 2) cut[rt] = true;}}int ans1 = 0;ll ans2 = 1;mark = 0;memset(vis, 0, sizeof(vis));for(int i=1; i<=n; i++){if(!vis[i] && !cut[i]){num = 0;ge_num = 0;++mark;dfs(i);if(ge_num == 0){ans1 += 2;ans2 *= 1ll*(num-1)*num/2;}else if(ge_num == 1){ans1 += 1;ans2 *= num; }}}printf("Case %d: %d %lld\n",++cas, ans1, ans2);} return 0; } View Code

?

轉載于:https://www.cnblogs.com/ckxkexing/p/10386356.html

總結

以上是生活随笔為你收集整理的P3225 [HNOI2012]矿场搭建 割点 tarjan 双联通分量的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。