AC. 梦想

图论目录下的文章

[CTSC 2016] 时空旅行

题意简述 有n个时空,第i个时空继承于第f_i个时空,并在此基础上加入或删除了某一个星球。 星球以三维坐标(x_i,y_i,z_i)表示,且每个星球有一个参数c_i。 有q个询问。每次选定一个时空s和一个平面x = x_0。求从该平面出发可到达的花费最小的星球。 到一个星球i的花费为(x_0 - x_……
17/04/24 | 暂无评论 | 504阅读 阅读详情

[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……
17/04/16 | 暂无评论 | 373阅读 阅读详情

[ZJOI 2017] 仙人掌

题意简述 给定n点m边的简单无向连通图。 现在要在图上加若干边,要求加边后还是一个简单无向连通图,且每条边至多属于一个简单环。 求加边方案数对998244353取模的值。 1 \le n \le 5 \times 10 ^ 5, 1 \le m \le 10 ^ 6 算法讨论 考后再写一遍的时候发现写的好快啊QAQ 先判一下……
17/03/25 | 暂无评论 | 699阅读 阅读详情

[WC 2013] 平面图

题意简述 给定n个点m条边的连通平面图,边有权值。 现在有q个询问。求连接平面上两点的一条曲线,不能经过无穷大区域,且曲线经过边的最大权值尽量小,询问最小值。 保证询问的点不在平面图的点和边上,且询问点的坐标是0.5的奇数倍,平面图点的坐标是0.5的偶数倍。 5 \le n, m ……
16/12/21 | 暂无评论 | 551阅读 阅读详情

[NOI 2016] 网格

题目描述 跳蚤国王和蛐蛐国王在玩一个游戏。 他们在一个n行m列的网格上排兵布阵。其中的c个格子中(0 \le c \le nm),每个格子有一只蛐蛐,其余的格子中,每个格子有一只跳蚤。 我们称占据的格子有公共边的两只跳蚤是相邻的。 我们称两只跳蚤是连通的,当且仅当这两只跳蚤相邻,……
16/08/06 | 暂无评论 | 1,231阅读 阅读详情

[NOIP 2015] 运输计划

题目描述 公元 2044 年,人类进入了宇宙纪元。 L 国有n个星球,还有n-1条双向航道,每条航道建立在两个星球之间,这n-1条航道连通了 LL 国的所有星球。 小 P 掌管一家物流公司, 该公司有很多个运输计划,每个运输计划形如:有一艘物流飞船需要从u_i号星球沿最快的宇航路径飞行……
16/05/12 | 暂无评论 | 772阅读 阅读详情

[ZJOI 2015] 幻想乡战略游戏

题目描述 傲娇少女幽香正在玩一个非常有趣的战略类游戏,本来这个游戏的地图其实还不算太大,幽香还能管得过来,但是不知道为什么现在的网游厂商把游戏的地图越做越大,以至于幽香一眼根本看不过来,更别说和别人打仗了。 在打仗之前,幽香现在面临一个非常基本的管理问题需要……
16/04/10 | 暂无评论 | 2,031阅读 阅读详情

[BZOJ 1095] 捉迷藏

题目描述 捉迷藏 Jiajia和Wind是一对恩爱的夫妻,并且他们有很多孩子。某天,Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特,由N个屋子和N-1条双向走廊组成,这N-1条走廊的分布使得任意两个屋子都互相可达。游戏是这样进行的,孩子们负责躲藏,Jiajia……
16/03/23 | 暂无评论 | 563阅读 阅读详情

割点和桥

这是我基础图论知识的一块漏洞,现在补上~~ 先来看割点的定义: 对于无向图G,如果删除某个点u后,连通分量数目增加,则称点u是图G的割点。 怎样求出一个图所有的割点呢?不难想到一个O(n(n+m))的做法,但这显然不是最优的,考虑其他思路。 我们考虑一个无向图的DFS树,发现无……
16/03/13 | 暂无评论 | 1,261阅读 阅读详情

[BZOJ 1468] Tree

题目描述 给你一棵树,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K。 输入格式 N(n<=40000) 接下来n-1行边描述管道,按照题目中写的输入,接下来是K。 输出格式 共一行,有多少对点之间的距离小于等于K。 题目解析 很经典的一道题目,算是树分治的入门题吧……
16/02/28 | 暂无评论 | 495阅读 阅读详情