祝馀宫

题面：Redundant Paths G大秦为你打开题目传送门 题面翻译为了从 $F(1 \le F \le 5000)$ 个草场中的一个走到另一个，贝茜和她的同伴们有时不得不路过一些她们讨厌的可怕的树．奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择。 每对草场之间已经有至少一条路径．给出所有 $R\ (F-1 \le R \le 10000)$ 条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量，路径由若干道路首尾相连而成．两条路径相互分离，是指两条路径没有一条重合的道路．但是，两条分离的路径上可以有一些相同的草场．对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路。 题目描述In order to get from one of the F (1 <= F <= 5,000) grazing fields (which are numbered 1..F) to another field, Bessie and the re ...

题面：[POI2008] BLO-Blockade大秦为你打开题目传送门 题面翻译B 城有 $n$ 个城镇（从 $1$ 到 $n$ 标号）和 $m$ 条双向道路。 每条道路连结两个不同的城镇，没有重复的道路，所有城镇连通。 把城镇看作节点，把道路看作边，容易发现，整个城市构成了一个无向图。 请你对于每个节点 $i$ 求出，把与节点 $i$ 关联的所有边去掉以后（不去掉节点 $i$ 本身），无向图有多少个有序点 $(x,y)$，满足 $x$ 和 $y$ 不连通。 【输入格式】 第一行包含两个整数 $n$ 和 $m$。 接下来 $m$ 行，每行包含两个整数 $a$ 和 $b$，表示城镇 $a$ 和 $b$ 之间存在一条道路。 【输出格式】 输出共 $n$ 行，每行输出一个整数。 第 $i$ 行输出的整数表示把与节点 $i$ 关联的所有边去掉以后（不去掉节点 $i$ 本身），无向图有多少个有序点 $(x,y)$，满足 $x$ 和 $y$ 不连通。 【数据范围】 $n\le 100000$，$m\le500000$。 题目描述There are exactly $n$ towns in By ...

题面：[ZJOI2004] 嗅探器大秦为你打开题目传送门 题目描述某军搞信息对抗实战演习，红军成功地侵入了蓝军的内部网络。 蓝军共有两个信息中心，红军计划在某台中间服务器上安装一个嗅探器，从而能够侦听到两个信息中心互相交换的所有信息。 但是蓝军的网络相当的庞大，数据包从一个信息中心传到另一个信息中心可以不止有一条通路。 现在需要你尽快地解决这个问题，应该把嗅探器安装在哪个中间服务器上才能保证所有的数据包都能被捕获？ 输入格式输入文件的第一行一个整数 $n$，表示蓝军网络中服务器的数目。 接下来若干行是对蓝军网络的拓扑结构描述，每行是两个整数 $i,j$ 表示编号为 $i$ 和编号为 $j$ 的两台服务器间存在双向连接。 服务器的编号从 $1$ 开始，一行两个 $0$ 表示网络的拓扑结构描述结束，再接下来是两个整数 $a,b$ 分别表示两个中心服务器的编号。 输出格式输出满足条件的服务器编号。如果有多个解输出编号最小的一个，如果找不到任何解，输出 No solution。 样例 #1样例输入 #112345678952 12 51 45 32 35 10 04 2 样例输出 #111 ...

题面：[HNOI2012] 矿场搭建大秦为你打开题目传送门 题目描述煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。 请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。 输入格式输入文件有若干组数据。 每组数据的第一行是一个正整数 $N\ (N \le 500)$，表示工地的隧道数。 接下来的 $N$ 行每行是用空格隔开的两个整数 $S$ 和 $T$，表示挖煤点 $S$ 与挖煤点 $T$ 由隧道直接连接。 输入数据以 $0$ 结尾。 输出格式对于每组数据，输出一行。 第 $i$ 行组数据以 Case i: 开始。 其后是用空格隔开的两个正整数，第一个正整数表示对于第 $i$ 组输入数据至少需要设置几个救援出口，第二个正整数表示对于第 $i$ 组输入数据不同最少救援出口的设置方案总数。 输入数据保证答案小于 $2^{64}$。输出格式参照以下输入输出样例。 样例 # ...

题面：间谍网络大秦为你打开题目传送门 题目描述由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果 A 间谍手中掌握着关于 B 间谍的犯罪证据，则称 A 可以揭发 B。有些间谍收受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以，如果我们能够收买一些间谍的话，我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍，他手中掌握的情报都将归我们所有，这样就有可能逮捕新的间谍，掌握新的情报。 我们的反间谍机关提供了一份资料，包括所有已知的受贿的间谍，以及他们愿意收受的具体数额。同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。假设总共有 $n$ 个间谍（$n$ 不超过 $3000$），每个间谍分别用 $1$ 到 $3000$ 的整数来标识。 请根据这份资料，判断我们是否有可能控制全部的间谍，如果可以，求出我们所需要支付的最少资金。否则，输出不能被控制的一个间谍。 输入格式第一行只有一个整数 $n$。 第二行是整数 $p$。表示愿意被收买的人数，$1\le p\le n$。 接下来的 $p$ 行，每行有两个整数，第一个数是一个愿意被收买的间谍的编号，第二个 ...

题面：[USACO5.3] Network of Schools大秦为你打开题目传送门 题目描述一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意即使 $B$ 在 $A$ 学校的分发列表中，$A$ 也不一定在 $B$ 学校的列表中。 你要写一个程序计算，根据协议，为了让网络中所有的学校都用上新软件，必须接受新软件副本的最少学校数目（子任务 A）。更进一步，我们想要确定通过给任意一个学校发送新软件，这个软件就会分发到网络中的所有学校。为了完成这个任务，我们可能必须扩展接收学校列表，使其加入新成员。计算最少需要增加几个扩展，使得不论我们给哪个学校发送新软件，它都会到达其余所有的学校（子任务 B）。一个扩展就是在一个学校的接收学校列表中引入一个新成员。 输入格式输入文件的第一行包括一个正整数 $N$，表示网络中的学校数目。学校用前 $N$ 个正整数标识。 接下来 $N$ 行中每行都表示一个接收学校列表（分发列表），第 $i+1$ 行包括学校 $i$ 的接收学校的标识符。每个列表用 $0$ 结束，空列表只用一个 $0$ 表示。 输出 ...

题面：[USACO03FALL] 受欢迎的牛 G大秦为你打开题目传送门 题目背景本题测试数据已修复。 题目描述每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 $A$ 喜欢 $B$，$B$ 喜欢 $C$，那么 $A$ 也喜欢 $C$。牛栏里共有 $N$ 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。 输入格式第一行：两个用空格分开的整数：$N$ 和 $M$。 接下来 $M$ 行：每行两个用空格分开的整数：$A$ 和 $B$，表示 $A$ 喜欢 $B$。 输出格式一行单独一个整数，表示明星奶牛的数量。 样例 #1样例输入 #112343 31 22 12 3 样例输出 #111 提示只有 $3$ 号奶牛可以做明星。 【数据范围】 对于 $10\%$ 的数据，$N\le20$，$M\le50$。 对于 $30\%$ 的数据，$N\le10^3$，$M\le2\times 10^4$。 对于 $70\%$ 的数据，$N\le5\times 10^3$，$M\le5\ ...

题面：[ZJOI2007] 最大半连通子图大秦为你打开题目传送门 题目描述一个有向图 $G=\left(V,E\right)$ 称为半连通的 (Semi-Connected)，如果满足：$\forall u,v\in V$，满足 $u\to v$ 或 $v\to u$，即对于图中任意两点 $u,v$，存在一条 $u$ 到 $v$ 的有向路径或者从 $v$ 到 $u$ 的有向路径。 若 $G’=\left(V’,E’\right)$ 满足 $V’\subseteq V$，$E’$ 是 $E$ 中所有跟 $V’$ 有关的边，则称 $G’$ 是 $G$ 的一个导出子图。若 $G’$ 是 $G$ 的导出子图，且 $G’$ 半连通，则称 $G’$ 为 $G$ 的半连通子图。若 $G’$ 是 $G$ 所有半连通子图中包含节点数最多的，则称 $G’$ 是 $G$ 的最大半连通子图。 给定一个有向图 $G$，请求出 $G$ 的最大半连通子图拥有的节点数 $K$，以及不同的最大半连通子图的数目 $C$。由于 $C$ 可能比较大，仅要求输出 $C$ 对 $X$ 的余数。 输入格式第一行包含两个整数 $N ...