分类
标签
2-SAT AC自动机 BFS CDQ dfs DP fail树 FFT FFT&NTT FWT hash KD-Tree KMP LCA SPFA STL Tarjan Treap Trie 主席树 乱搞 二分 二分图匹配 二分答案 二维SPFA 交互 位运算 其他 最小生成树 分块 区间DP 半平面交 博弈论 可持久化 可持久化Trie树 后缀数组 图库 平衡树 并查集 插头DP 数学 数论 无旋Treap 日记 暴力 权值树状数组 栈 树DP 树套树 树状数组 树贪心 概率DP 模拟 欧拉定理 点分治 状压DP 生成函数 矩阵乘 线性规划 线段树 组合 网络流 群论 莫比乌斯反演 计算几何 贪心 费用流 高斯消元
835 字
4 分钟
[HNOI2012]矿场搭建
题目描述
煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。请写一个程序,用来计算至少需要设置几个救援出口,以及不同最少救援出口的设置方案总数。
输入 输入文件有若干组数据,每组数据的第一行是一个正整数 N(N≤500),表示工地的隧道数,接下来的 N 行每行是用空格隔开的两个整数 S 和 T,表示挖S 与挖煤点 T 由隧道直接连接。输入数据以 0 结尾。
输出
输入文件中有多少组数据,输出文件 output.txt 中就有多少行。每行对应一组输入数据的 结果。其中第 i 行以 Case i: 开始(注意大小写,Case 与 i 之间有空格,i 与:之间无空格,: 之后有空格),其后是用空格隔开的两个正整数,第一个正整数表示对于第 i 组输入数据至少需 要设置几个救援出口,第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总 数。输入数据保证答案小于 2^64。输出格式参照以下输入输出样例。
样例输入
9
1 3
4 1
3 5
1 2
2 6
1 5
6 3
1 6
3 2
6
1 2
1 3
2 4
2 5
3 6
3 7
0
样例输出
Case 1: 2 4
Case 2: 4 1
题解
可也看出如果塌在割点才有影响
所以先跑出所以割点,然后删去割点跑联通块
如果一个块有两个割点那么无所谓。 否则建一个方案为点数
最后如果只要一个联通块,那么就要两个点。方案数为n*(n-1)/2
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct edge
{
int END, next;
} v[10005];
int first[500], p;
void add(int a, int b)
{
v[p].END = b;
v[p].next = first[a];
first[a] = p++;
}
int dfn[500], low[500], Index;
bool iscut[500];
void Tarjan(int x, int fa)
{
low[x] = dfn[x] = ++Index;
int S = 0;
for (int i = first[x]; i != -1; i = v[i].next)
{
if (!dfn[v[i].END])
{
S++;
Tarjan(v[i].END, x);
low[x] = min(low[v[i].END], low[x]);
if (low[v[i].END] >= dfn[x])
iscut[x] = 1;
}
else
low[x] = min(low[x], dfn[v[i].END]);
}
if (fa < 0 && S == 1)
iscut[x] = 0;
}
bool vis[500];
int T, size, num;
int color[500];
void dfs(int x)
{
vis[x] = 1;
size++;
for (int i = first[x]; i != -1; i = v[i].next)
{
if (!vis[v[i].END])
{
if (!iscut[v[i].END])
dfs(v[i].END);
else
{
if (color[v[i].END] != T)
color[v[i].END] = T, num++;
}
}
}
}
int main()
{
//freopen("bzoj_2730.in","r",stdin);
//freopen("bzoj_2730.out","w",stdout);
int P1 = 0;
while (1)
{
memset(vis, 0, sizeof(vis));
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(iscut, 0, sizeof(iscut));
memset(first, -1, sizeof(first));
memset(color, 0, sizeof(color));
p = 0;
Index = 0;
P1++;
int n = 0, a, b, m;
scanf("%d", &m);
if (m == 0)
break;
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &a, &b);
n = max(a, n);
n = max(b, n);
add(a, b);
add(b, a);
}
for (int i = 1; i <= n; i++)
if (!dfn[i])
Tarjan(i, -1);
int ans1 = 0;
long long ans2 = 1;
T = 0;
for (int i = 1; i <= n; i++)
{
if (!vis[i] && !iscut[i])
{
T++, size = 0, num = 0;
dfs(i);
if (num == 1)
ans1++, ans2 *= size;
}
}
if (T == 1)
ans1 = 2, ans2 = n * (n - 1) / 2;
printf("Case %d: %d %lld\n", P1, ans1, ans2);
}
}