博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
LA 5135 井下矿工
阅读量:5815 次
发布时间:2019-06-18

本文共 2029 字,大约阅读时间需要 6 分钟。

题目链接:

白书P318

题目大意:有N个矿井 ,由一些隧道连接起来,现在要修建尽量少的安全通道,使得无论哪里发生事故,所有人均能逃出,求建的最少的安全通道数量和方案数.

 

分情况讨论:

 

在一个无向图上选择尽量少的点涂黑,是的任意删除一个点后,每个连通分量都有一个黑点。

第一种情况:点-双连通里面没有割顶,那么至少要涂两个。

第二种情况:有一个割顶,那么割顶一定是不要涂黑的。涂黑了割顶,割顶删掉,那么在那个点-双连通里面还得加一个点涂黑。

第三种情况:有两个或两个以上的割顶,那么,一个点删掉以后,其他点都可以通过另外的割顶逃到相应的黑点上去。

 

求出点-双连通以后,查每个点-双连通分量的割顶数目就行了。

#include 
using 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

 

转载于:https://www.cnblogs.com/TreeDream/p/6074973.html

你可能感兴趣的文章
Redis之七种武器
查看>>
Configuring the JA-SIG CAS Client --官方
查看>>
【前端开发系列】—— CSS3属性选择器总结
查看>>
深入理解php 匿名函数和 Closure
查看>>
CentOS 网络设置修改 指定IP地址 DNS 网关(实测 笔记)
查看>>
怎样使用SetTimer MFC 够具体
查看>>
【原】我是超级收银员,你敢来挑战吗
查看>>
jquery获取radio值
查看>>
ViewPager介绍和使用说明
查看>>
HBase的安装与使用
查看>>
Eclipse 工程Clear与build的作用
查看>>
用python做自己主动化測试--对server端的自己主动化測试(3)-很多其它http client实例...
查看>>
Ubuntu系统安装stardict(星际译王)词典
查看>>
Es分析
查看>>
20个经典bootsrtap后台html站点模板推荐
查看>>
美容实用小知识
查看>>
控制台输入输出机制实例
查看>>
UVa 673 Parentheses Balance (stack)
查看>>
一根山药的六大功效
查看>>
用计算器计算“异或CRC”
查看>>