首页 > [HNOI2012]矿场搭建
开通博客写题解
头像 苟且的狮子
发表于 2020-08-29 23:06:09
tarjan、割点、分类讨论 题意： 分析： 这题很容易让我们想到割点。这并不难，但是细节上的处理于分类讨论才是这道题的难点。 我们想想如果一个连通块，他有一个割点。 那么，我们一定要在他被割点分开的两个连通块中放置救援出口。而放置的方案数就是两边的点数相乘，割点不算！ 如果，他有两个以上的割点 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 hnust_yangyanjun
发表于 2021-01-29 13:55:31
题意：给出n条边，求该图至少需要设置多少个逃生点才能使无论哪一个点失去，其余点都能至少到达一个逃生点，并求出方案数。 思路：考虑点双连通分量：如果该点双连通分量只有一个割点，则需要设一个逃生点，且该点不能是割点（防止唯一的割点失去时其余点无法到达逃生点）。如果该点双连通分量有大于一个割点，则无需设置 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 sunrise__sunrise
发表于 2021-01-28 00:12:17
题目描述 每组输入第一行一个整数,代表后面出现的条路径。给出这样的一个无向图，如果你可以放置逃生通道在容易一个点处，也可以放置任意数量的逃生通道，现在询问最少的逃生通道个数是几个，并且保证通道个数最少的情况下，有几种放置方案使得全部人在图中随机某个点消失的情况下也可以顺利逃生。 。 居然给出的是一个 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 minux_sufe
发表于 2020-07-03 19:19:59
#include <bits/stdc++.h> using namespace std; typedef unsigned long long ULL; const int N=1005; const int M=1005; int n, m; int head[N], E=0; 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 熠丶
发表于 2021-01-26 03:09:47
题意 给定一个无向图，问最少在几个点上设置出口，可以使得不管哪个点坍塌，其余所有点都可以与某个出口连通。求设置出口的数量及方案数。 做法：Tarjan，割点 前置芝士：割点 思路： 目前可公开情报：1.孤点：数量+1，方案数不变2.连通块无割点：数量+2，方案数3.连通块存在一个割点，数量+1 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 回归梦想
发表于 2021-01-14 17:09:13
NC20099 [HNOI2012]矿场搭建 题目： • 煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。• 于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。• 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”