LA 5135 井下矿工

题目链接:http://vjudge.net/contest/141787#problem/B

白书P318

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

分情况讨论:

LA 5135 井下矿工

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

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

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

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

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

#include <bits/stdc++.h>
using namespace std; const int maxn = *; int n;
struct Edge
{
int u,v;
}; int pre[maxn], iscut[maxn], bccno[maxn], dfs_clock, bcc_cnt;
vector<int> G[maxn], bcc[maxn]; stack<Edge> S; int dfs(int u, int fa)
{
int lowu = pre[u] = ++dfs_clock;
int child = ;
for(int i = ; 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 < && child == ) iscut[u] = ;
return lowu;
} void find_bcc(int n)
{ memset(pre,,sizeof(pre));
memset(iscut,,sizeof(iscut));
memset(bccno,,sizeof(bccno)); dfs_clock = bcc_cnt = ;
for(int i=; i<n; i++)
{
if(!pre[i])
dfs(i,-);
} } int main()
{
int kase = ;
while(scanf("%d",&n),n)
{
for(int i=; i<n*; i++)
{
G[i].clear();
} for(int i=; i<n; i++)
{ int u,v;
scanf("%d%d",&u,&v);
u--;
v--; G[u].push_back(v);
G[v].push_back(u); } //求点-双连通分量
find_bcc(n); long long ans1 = ,ans2 = ;
for(int i=; i<=bcc_cnt; i++)
{
int cut_cnt = ;
for(int j=; j<bcc[i].size(); j++)
{
if(iscut[bcc[i][j]])
cut_cnt ++;
}
if(cut_cnt==)
{
ans1 ++;
ans2 = ans2 * (bcc[i].size()-cut_cnt);
}
}
if(bcc_cnt==)
{
ans1 = ;
ans2 = bcc[].size() * (bcc[].size()-)/;
}
printf("Case %d: %lld %lld\n",kase++,ans1,ans2); } return ;
}
上一篇:js replace 全局替换 以表单的方式提交参数 判断是否为ie浏览器 将jquery.qqFace.js表情转换成微信的字符码 手机端省市区联动 新字体引用本地运行可以获得,放到服务器上报404 C#提取html中的汉字 MVC几种找不到资源的解决方式 使用Windows服务定时去执行一个方法的三种方式


下一篇:2.1 自定义日志系统-log4net