# Floyd

Acwing379 捉迷藏

原题链接:Acwing379

题目描述:Vani 和 cl2 在一片树林里捉迷藏。

这片树林里有 N 座房子,M 条有向道路,组成了一张有向无环图。

树林里的树非常茂密,足以遮挡视线,但是沿着道路望去,却是视野开阔。

如果从房子 A 沿着路走下去能够到达 B,那么在 A 和 B 里的人是能够相互望见的。

现在 cl2 要在这 N 座房子里选择 K 座作为藏身点,同时 Vani 也专挑 cl2 作为藏身点的房子进去寻找,为了避免被 Vani 看见,cl2 要求这 K 个藏身点的任意两个之间都没有路径相连。

为了让 Vani 更难找到自己,cl2 想知道最多能选出多少个藏身点。

……

READ MORE

Acwing345 牛站

原题链接:Acwing345

题目大意:给定一张由T条边构成的无向图,点的编号为1~1000之间的整数。

求从起点 S 到终点 E 恰好经过 N 条边(可以重复经过)的最短路。

……

READ MORE

Acwing344 观光之旅

原题链接:Acwing344

题目大意:给定一张无向图,求图中一个至少包含3个点的环,环上的节点不重复,并且环上的边的长度之和最小。该问题称为无向图的最小环问题。你需要输出最小环的方案,若最小环不唯一,输出任意一个均可。

……

READ MORE

Acwing343 排序

原题链接:Acwing343

题目大意:给定 $n$个变量和 $m$ 个不等式。其中 $n$ 小于等于$26$,变量分别用前 $n$ 的大写英文字母表示。不等式之间具有传递性,即若 $A>B$ 且 $B>C $,则$ A>C$。

请从前往后遍历每对关系,每次遍历时判断:

  • 如果能够确定全部关系且无矛盾,则结束循环,输出确定的次序;
  • 如果发生矛盾,则结束循环,输出有矛盾;
  • 如果循环结束时没有发生上述两种情况,则输出无定解。
……

READ MORE

Acwing1125 牛的旅行

原题链接:Acwing1125

题目大意:给定两个不连通的牧场,每个牧场内部的牧区连通, 一个牧场的直径就是牧场中最远的两个牧区的距离(本题中所提到的所有距离指的都是最短的距离)。 现在,John想在农场里添加一条路径 , 连接两个原本不连通的牧场,使得连上这条路径后,这个更大的新牧场有最小的直径。 求这个直径。

……

READ MORE

Recents
Categories
Tags
Links