图论目录下的文章
[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
NOI前50天日记
[BZOJ 1013] 球形空间产生器
梦在信息学
[SDOI 2016] 生成魔咒