图论目录下的文章
[CTSC 2016] 时空旅行
题意简述
有n个时空,第i个时空继承于第f_i个时空,并在此基础上加入或删除了某一个星球。
星球以三维坐标(x_i,y_i,z_i)表示,且每个星球有一个参数c_i。
有q个询问。每次选定一个时空s和一个平面x = x_0。求从该平面出发可到达的花费最小的星球。
到一个星球i的花费为(x_0 - x_……
[APIO 2015] Jakarta Skyscrapers
题意简述
有n个点和m只doge。
第i只doge在x_i位置,跳跃能力为v_i。
设在某时刻,第i只doge在点p,它能够
1. 跳到p - v_i或p + v_i(若存在)。
2. 把携带的消息告诉在这个点的doge。
现在第0只doge有一条消息,求所有doge总共最少跳跃多少步能够将消息传达到第1只doge呢?
1 \l……
[ZJOI 2017] 仙人掌
题意简述
给定n点m边的简单无向连通图。
现在要在图上加若干边,要求加边后还是一个简单无向连通图,且每条边至多属于一个简单环。
求加边方案数对998244353取模的值。
1 \le n \le 5 \times 10 ^ 5, 1 \le m \le 10 ^ 6
算法讨论
考后再写一遍的时候发现写的好快啊QAQ
先判一下……
[WC 2013] 平面图
题意简述
给定n个点m条边的连通平面图,边有权值。
现在有q个询问。求连接平面上两点的一条曲线,不能经过无穷大区域,且曲线经过边的最大权值尽量小,询问最小值。
保证询问的点不在平面图的点和边上,且询问点的坐标是0.5的奇数倍,平面图点的坐标是0.5的偶数倍。
5 \le n, m ……
[NOI 2016] 网格
题目描述
跳蚤国王和蛐蛐国王在玩一个游戏。
他们在一个n行m列的网格上排兵布阵。其中的c个格子中(0 \le c \le nm),每个格子有一只蛐蛐,其余的格子中,每个格子有一只跳蚤。
我们称占据的格子有公共边的两只跳蚤是相邻的。
我们称两只跳蚤是连通的,当且仅当这两只跳蚤相邻,……
[NOIP 2015] 运输计划
题目描述
公元 2044 年,人类进入了宇宙纪元。
L 国有n个星球,还有n-1条双向航道,每条航道建立在两个星球之间,这n-1条航道连通了 LL 国的所有星球。
小 P 掌管一家物流公司, 该公司有很多个运输计划,每个运输计划形如:有一艘物流飞船需要从u_i号星球沿最快的宇航路径飞行……
[ZJOI 2015] 幻想乡战略游戏
题目描述
傲娇少女幽香正在玩一个非常有趣的战略类游戏,本来这个游戏的地图其实还不算太大,幽香还能管得过来,但是不知道为什么现在的网游厂商把游戏的地图越做越大,以至于幽香一眼根本看不过来,更别说和别人打仗了。
在打仗之前,幽香现在面临一个非常基本的管理问题需要……
[BZOJ 1095] 捉迷藏
题目描述
捉迷藏 Jiajia和Wind是一对恩爱的夫妻,并且他们有很多孩子。某天,Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特,由N个屋子和N-1条双向走廊组成,这N-1条走廊的分布使得任意两个屋子都互相可达。游戏是这样进行的,孩子们负责躲藏,Jiajia……
割点和桥
这是我基础图论知识的一块漏洞,现在补上~~
先来看割点的定义:
对于无向图G,如果删除某个点u后,连通分量数目增加,则称点u是图G的割点。
怎样求出一个图所有的割点呢?不难想到一个O(n(n+m))的做法,但这显然不是最优的,考虑其他思路。
我们考虑一个无向图的DFS树,发现无……
[BZOJ 1468] Tree
题目描述
给你一棵树,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K。
输入格式
N(n<=40000) 接下来n-1行边描述管道,按照题目中写的输入,接下来是K。
输出格式
共一行,有多少对点之间的距离小于等于K。
题目解析
很经典的一道题目,算是树分治的入门题吧……
12