题目链接:
白书P318
题目大意:有N个矿井 ,由一些隧道连接起来,现在要修建尽量少的安全通道,使得无论哪里发生事故,所有人均能逃出,求建的最少的安全通道数量和方案数.
分情况讨论:
在一个无向图上选择尽量少的点涂黑,是的任意删除一个点后,每个连通分量都有一个黑点。
第一种情况:点-双连通里面没有割顶,那么至少要涂两个。
第二种情况:有一个割顶,那么割顶一定是不要涂黑的。涂黑了割顶,割顶删掉,那么在那个点-双连通里面还得加一个点涂黑。
第三种情况:有两个或两个以上的割顶,那么,一个点删掉以后,其他点都可以通过另外的割顶逃到相应的黑点上去。
求出点-双连通以后,查每个点-双连通分量的割顶数目就行了。
#includeusing namespace std;const int maxn = 50005*2;int n;struct Edge{ int u,v;};int pre[maxn], iscut[maxn], bccno[maxn], dfs_clock, bcc_cnt;vector G[maxn], bcc[maxn];stack S;int dfs(int u, int fa){ int lowu = pre[u] = ++dfs_clock; int child = 0; for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; Edge e = (Edge) { u, v }; if(!pre[v]) // 没有访问过v { S.push(e); child++; int lowv = dfs(v, u); lowu = min(lowu, lowv); // 用后代的low函数更新自己 if(lowv >= pre[u]) { iscut[u] = true; bcc_cnt++; bcc[bcc_cnt].clear(); for(;;) { Edge x = S.top(); S.pop(); if(bccno[x.u] != bcc_cnt) { bcc[bcc_cnt].push_back(x.u); bccno[x.u] = bcc_cnt; } if(bccno[x.v] != bcc_cnt) { bcc[bcc_cnt].push_back(x.v); bccno[x.v] = bcc_cnt; } if(x.u == u && x.v == v) break; } } } else if(pre[v] < pre[u] && v != fa) { S.push(e); lowu = min(lowu, pre[v]); // 用反向边更新自己 } } if(fa < 0 && child == 1) iscut[u] = 0; return lowu;}void find_bcc(int n){ memset(pre,0,sizeof(pre)); memset(iscut,0,sizeof(iscut)); memset(bccno,0,sizeof(bccno)); dfs_clock = bcc_cnt = 0; for(int i=0; i