首页 > 其他分享 >矿场搭建 题解

矿场搭建 题解

时间:2024-03-16 12:22:25浏览次数:23  
标签:矿场 int 题解 memset dfn low sizeof include 搭建

题目描述

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。

请写一个程序,用来计算至少需要设置几个救援出口,以及不同最少救援出口的设置方案总数。

输入格式

image

输出格式

输入文件中有多少组数据,输出文件中就有多少行。每行对应一组输入数据的结果。

其中第 i 行以 Case i: 开始(注意大小写,Case 与 i 之间有空格,i 与 : 之间无空格,: 之后有空格),其后是用空格隔开的两个正整数,第一个正整数表示对于第 组输入数据至少需要设置几个救援出口,第二个正整数表示对于第 组输入数据不同最少救援出口的设置方案总数。

输出格式参照以下输入输出样例。

样例

样例输入

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

image

题解

这是一张无向图,我们可以发现,对于它的一个子图D,如果D中任意两点都联通,那么我们就可以将D缩成一个点,然后在进行操作,这不就是Tarjan求点双连通分量吗;

求完以后,很显然,点双的个数就是我们要找的最少出口个数(这里不再过多进行解释);

对于第二问,应该如何处理呢?

我们知道,每个D中可能会有0,1,2...个对于整张图的割点(点双性质),对于这几种情况,我们可以分别讨论;

  1. 当割点个数为0时,很显然,整张图是点双,可以得出最少出口个数为2(因为当一个出口塌了的时候,还可以从另一个出去),方案数为m * (m - 1) >> 1(其中m为点数,从m个点中选两个,用排列即可解决);

image

  1. 当割点个数为1时,我们只需在每个D中建一个不是割点的出口即可;

证明:当割点塌了时,可以从D中的出口出;当出口塌了时,可以从割点去其他的D中出

image

  1. 当割点个数>1时,不用设出口,因为从D中可以去至少2个其它的D出去;

image

上述图片转载自https://www.cnblogs.com/Charlieljk/p/17888945.html

如果还是看不懂,去搜搜Tarjan求点双

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
struct sss{
	int t, ne;
}e[500005];
int h[500005], cnt;
void add(int u, int v) {
	e[++cnt].ne = h[u];
	h[u] = cnt;
	e[cnt].t = v;
}
int dfn[500005], low[500005];
int num;
stack<int> s;
vector<int> ds[500005];
vector<int> a;
bool cd[500005];
int dcnt;
void tarjan(int x, int root, int fa) { //Tarjan求点双联通分量;
	dfn[x] = low[x] = ++num;
	s.push(x);
	int son = 0;
	bool first = true;
	for (int i = h[x]; i; i = e[i].ne) {
		int u = e[i].t;
		if (first && u == fa) {
			first = false;
			continue;
		}
		if (!dfn[u]) {
			son++;
			tarjan(u, root, x);
			low[x] = min(low[x], low[u]);
			if (low[u] >= dfn[x]) {
				if (x != root || son > 1) {
					cd[x] = true;
				}
					dcnt++;
					ds[dcnt].push_back(x);
					int t = 0;
					do {
						t = s.top();
						s.pop();
						ds[dcnt].push_back(t);
					} while(t != u);
			}
		} else {
			low[x] = min(low[x], dfn[u]);
		}
	}
	return;
}
int main() {
	scanf("%d", &n);
	int ssum = 0;
	while(n) {
		int x, y;
		ssum++;
		memset(dfn, 0, sizeof(dfn));
		memset(low, 0, sizeof(low));
		cnt = 0;
		num = 0;
		dcnt = 0;
		long long ans = 0;
		long long an = 1;
		memset(h, 0, sizeof(h));
		memset(e, 0, sizeof(e));
		memset(cd, 0, sizeof(cd));
		memset(ds, 0, sizeof(ds));
		a.clear();
		while(!s.empty()) s.pop();
		for (int i = 1; i <= n; i++) {
			scanf("%d %d", &x, &y);
			add(x, y);
			add(y, x);
			a.push_back(x);
			a.push_back(y);
		}
		sort(a.begin(), a.end());
		m = unique(a.begin(), a.end()) - a.begin(); //m为点数;
		for (int i = 1; i <= m; i++) {
			if (!dfn[i]) tarjan(i, i, i);
		}
		for (int i = 1; i <= dcnt; i++) {
			int c = 0;
			for (int j = 0; j < ds[i].size(); j++) {
				if (cd[ds[i][j]]) c++;
			}
			if (c == 1) {
				ans++;
				an *= (ds[i].size() - 1);
			}
		}
		if (ds[1].size() == m) { //整张图是点双;
			ans = 2;
			an = ds[1].size() * (ds[1].size() - 1) >> 1;
		}
		printf("Case %d: %lld %lld\n", ssum, ans, an);
		scanf("%d", &n);
	}
	return 0;
}

标签:矿场,int,题解,memset,dfn,low,sizeof,include,搭建
From: https://www.cnblogs.com/PeppaEvenPig/p/18076931

相关文章

  • nodejs打包问题解决实例
    node命令集合npmsetregistryhttps://registry.npm.taobao.org/npmconfigsetregistryhttps://registry.npmjs.org/npmconfigsetsass_binary_sitehttps://npm.taobao.org/mirrors/node-sass/npmgetregistry //npm安装包的提示操作目录权限不足npmconfigsetu......
  • CF1948F 题解
    对于每个询问,可以把这\(r-l+1\)个袋子包合并成一个有\(\sum\limits_{i=l}^ra_i\)个金币和\(\sum\limits_{i=l}^rb_i\)个银币的袋子。\([l,r]\)外的袋子同理也可以这样合并。假设\(sum_a=\sum\limits_{i=1}^na_i,sum_b=\sum\limits_{i=1}^nb_i\),\(......
  • CF145C Lucky Subsequence 题解
    首先,我们对这个幸运数进行分析,发现:\(10^9\)以内只有\(1023\)个幸运数,即\(\sum\limits_{i=0}^92^i\)个。考虑对幸运数和非幸运数分类讨论。幸运数部分:01背包裸题,\(dp_{i,j}\)表示前\(i\)个幸运数里选了\(j\)个,转移方程为\(dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}\tim......
  • [HNOI2012] 矿场搭建 题解
    [HNOI2012]矿场搭建前置知识:#Tarjan求点双连通分量题目大意​ 给你一张无向连通图,任意删去其中一个点,要求在删点后在每个连通块中有一个点被选择,问至少需要选择多少个点,以及选择的方案数。输入输出格式输入​ 多组数据以\(N=0\)结束​ 每组数据第一行为边的数量\(N\(N......
  • NOI2021 轻重边 题解
    NOI2021轻重边题目链接:#4812.[NOI2021]轻重边前置知识:#树链剖分#线段树题目大意给定\(n\)个点组成的树,\(m\)次操作。修改操作会让路径\(a\tob\)上的所有点的所有连边对答案的贡献变为\(0\),路径\(a\tob\)的所有边的贡献变为\(1\);查询操作则统计路径\(a\tob\)的......
  • CF57C Array 题解
    发现单调不降序列反过来就是单调不增序列,只需考虑单调不降序列即可。假如将问题转化为:初始为\(1\),一共有\(n+1\)个位置,有\(n-1\)次增加答案的机会,每个位置可以拥有多次增加答案的机会,问一共有多少种可能性。显然答案为\(C_{2n-1}^{n-1}\)。所以总体答案为\(2C_{2n-1}^{n-......
  • P2824 [HEOI2016/TJOI2016] 排序 与 ABC297_g Range Sort Query 题解
    洛谷题目链接:排序abc题目链接:Atcoder或者洛谷两道差不多的题拿出来说说。本题有双\(\log\)做法,也有单\(\log\)做法,都讲讲。双\(\log\)做法对于第一个题而言,询问最终\(pos\)位置上的数为多少,那么这个问题是否具有单调性?这个是很有意思的点,我们考虑只关注某个数\(x\)......
  • 洛谷题解 - B3850 [GESP202306 四级] 幸运数
    目录题目描述输入格式输出格式样例#1样例输入#1样例输出#1代码题目描述小明发明了一种“幸运数”。一个正整数,其偶数位不变(个位为第111位,十位为第......
  • 教程|腾讯云高性能应用服务(HAI)搭建Stable Diffusion 文生图API
    本次我们使用腾讯云高性能应用服务HAI体验快速搭建并使用AI模型StableDiffusion,实现思路如下:提前通过高性能应用服务HAI部署成功StableDiffusion应用。基于部署好的应用,利用体验JupyterLab进行StableDiffusionAPI的部署。前提在部署API服务之前,请确保......
  • 炸弹题解
    这题有两种做法,一种tarjan,一种逆天DP用lower_bound或upper查找i所在范围的左右边界对应下标普通Tarjan+缩点#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=5e5+10,mod=1e9+7;intn,dfn[N],low[N],head2[N],num,cnt,head[N],belong[N];b......