分类目录:图论-连通性问题

以下是分类 图论-连通性问题 下的所有文章

Metropolis

链接:传送门 来源:牛客网 题目描述 魔方国有n座城市,编号为。城市之间通过n-1条无向道路连接,形成一个树形结构。 在若干年之后,其中p座城市发展成了大都会,道路的数量也增加到了m条。 大都会之间经常有贸易往来,因此,对于每座大都会,请你求出它到离它最近的其它大都会的距离。 输入描述: 第一行三个整数n,m,p (1 ≤ n,m ≤ 2……

New Game!

链接:传送门 来源:牛客网 题目描述 Eagle Jump公司正在开发一款新的游戏。Hifumi Takimoto作为其中的员工,获得了提前试玩的机会。现在她正在试图通过一个迷宫。 这个迷宫有一些特点。为了方便描述,我们对这个迷宫建立平面直角坐标系。迷宫中有两条平行直线 L1:Ax+By+C1=0, L2:Ax+By+C2=0,还有 n ……

balabala小魔法箱(缩点+BFS)

Description xkp很爱旅游。 他来到了一个二次元世界,这个世界有n个岛和m座桥。 这个世界的桥具有魔性,部分桥上有balabala小魔法箱,且桥在经过一次后就会断掉。 现在xkp在s岛,他想到达t岛,在前往t岛的过程中xkp想收集一些小魔法箱。 现在他想问你他能否在s-t的途中收集小魔法箱,如果能输出“YES“,否则输出“NO……