祝馀宫

题面：[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 ...

题面：最短路计数大秦为你打开题目传送门 题目描述给出一个 $N$ 个顶点 $M$ 条边的无向无权图，顶点编号为 $1\sim N$。问从顶点 $1$ 开始，到其他每个点的最短路有几条。 输入格式第一行包含 $2$ 个正整数 $N,M$，为图的顶点数与边数。 接下来 $M$ 行，每行 $2$ 个正整数 $x,y$，表示有一条连接顶点 $x$ 和顶点 $y$ 的边，请注意可能有自环与重边。 输出格式共 $N$ 行，每行一个非负整数，第 $i$ 行输出从顶点 $1$ 到顶点 $i$ 有多少条不同的最短路，由于答案有可能会很大，你只需要输出 $ ans \bmod 100003$ 后的结果即可。如果无法到达顶点 $i$ 则输出 $0$。 样例 #1样例输入 #1123456785 71 21 32 43 42 34 54 5 样例输出 #11234511124 提示$1$ 到 $5$ 的最短路有 $4$ 条，分别为 $2$ 条 $1\to 2\to 4\to 5$ 和 $2$ 条 $1\to 3\to 4\to 5$（由于 $4\to 5$ 的边有 $2$ 条）。 对于 $20\%$ 的数据 ...

题面：[USACO06NOV] Roadblocks G大秦为你打开题目传送门 题面翻译贝茜把家搬到了一个小农场，但她常常回到 FJ 的农场去拜访她的朋友。贝茜很喜欢路边的风景，不想那么快地结束她的旅途，于是她每次回农场，都会选择第二短的路径，而不象我们所习惯的那样，选择最短路。贝茜所在的乡村有 $R(1\le R \le 10^5)$ 条双向道路，每条路都联结了所有的 $N(1\le N\le 5000)$ 个农场中的某两个。贝茜居住在农场 $1$，她的朋友们居住在农场 $N$（即贝茜每次旅行的目的地）。贝茜选择的第二短的路径中，可以包含任何一条在最短路中出现的道路，并且，一条路可以重复走多次。当然咯，第二短路的长度必须严格大于最短路（可能有多条）的长度，但它的长度必须不大于所有除最短路外的路径的长度。 题目描述Bessie has moved to a small farm and sometimes enjoys returning to visit one of her best friends. She does not want to get to her old hom ...

题面：[USACO07FEB] Cow Party S大秦为你打开题目传送门 题目描述寒假到了，$n$ 头牛都要去参加一场在编号为 $x$ 的牛的农场举行的派对，农场之间有 $m$ 条有向路，每条路都有一定的长度。 每头牛参加完派对后都必须回家，无论是去参加派对还是回家，每头牛都会选择最短路径，求这 $n$ 头牛的最短路径（一个来回）中最长的一条路径长度。 输入格式第一行有三个整数，分别表示牛的数量 $n$，道路数 $m$ 和派对农场编号 $x$。接下来 $m$ 行，每行三个整数 $u, v, w$，表示存在一条由 $u$ 通向 $v$ 的长度为 $w$ 的道路。 输出格式输出一行一个整数表示答案。 样例 #1样例输入 #11234567894 8 21 2 41 3 21 4 72 1 12 3 53 1 23 4 44 2 3 样例输出 #1110 提示样例 1 解释 数据规模与约定对于全部的测试点，保证 $1 \leq x \leq n \leq 10^3$，$1 \leq m \leq 10^5$，$1 \leq u,v \leq n$，$1 \leq w \leq 10^2 ...

题面题目链接大秦 为你打开 题目传送门 题目翻译找出带权无向图图上至少有三个的最小环，若无解，输出 No Solution. ，图的节点数不超过 $100$ ，边数不超过 $10000$ ，每条边的权值小于等于 $500$ 且大于 $0$ 。 思路这个数据范围一眼顶针就是 Floyd 算法，但是我们如何去求最小环就变成了问题。我们考虑一个环是如何组成的（前提是环的一部分是最短路）见下图： 这样是一个环的组成部分，那么就可以用这个思路，去得到最小环的权值，但是问题现在又来了，如何得到环上的点。我们发现 Floyd 每次在进行松弛操作会有一个中转点，我们记录这个中转点，不断还原出原路径即可。 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021 ...

题面：[国家集训队] Tree I题目链接大秦为你打开题目传送门 题目描述给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有 $need$ 条白色边的生成树。 题目保证有解。 输入格式第一行 $V,E,need$ 分别表示点数，边数和需要的白色边数。 接下来 $E$ 行，每行 $s,t,c,col$ 表示这边的端点（点从 $0$ 开始标号），边权，颜色（$0$ 白色 $1$ 黑色）。 输出格式一行，表示所求生成树的边权和。 样例 #1样例输入 #11232 2 10 1 1 10 1 2 0 样例输出 #112 提示对于 $5\%$ 的数据，$V\leq 10$。 对于另 $15\%$ 的数据，$V\leq 15$。 对于 $100\%$ 的数据，$V\leq 5\times10^4,E\leq 10^5$。 所有数据边权为 $[1,100]$ 中的正整数。 By WJMZBMR 思路首先，要达到最小生成树固定颜色边的目的，最首要的部分就是控制权重。但是发现如果单一的规定白色边或者黑色边排在前面，满足不了一定是 need 条白色边的需求，所以不难想到枚举给白色边的加 ...