题目链接 题解 把人走的点当作左部节点，🐕走的当作右部 对于每个人走的节点，如果他与下一个节点的距离的两倍大于某个从当前节点走到右部节点+右部节点走到下一节点的距离，即可连边 输出方案的话，注意到如果右部节点被匹配，match[i]就是匹配它的左部节点，存起来输出即可 代码 [crayon-67eae5ff23488878407007/]

题目链接 题解 两眼题 考虑每一行，如果当前列为1，则行与列连边 于是我们左部是每一行，右部是列，可以发现，如果有解，当且仅当每一列都有行与之匹配 跑匈牙利即可 代码 [crayon-67eae5ff2377f972800873/]

题目链接 题目大意 有 $n$ 个学生 $m$ 个社团，每个学生有一个能力值 $p_i$ 属于 $c_i$ 社团，接下来的 $d$ 天里，每天由校长钦点一个学生滚蛋，然后由你从每个社团选一个人（没人就不选），对于每天，求这些人 $p_i$ 的 $mex$ 的最大值 $mex$ 即为序列中最小的非负整数 题解 考虑二分图匹配 左部为学生的能力值，右部…

题目链接 不得不说，网络流的题目其实实现起来都是套模板，但是要想到就很困难。 很多人学了最小割之后就来切这道“裸题”，数据范围小，还没要求输出具体方案，太简单了！ 但是最小割是适用于有向图，而且是边集，但是这道题是要我们找出点的个数，而且是无向图。 在看这篇题解的时候默认你知道“最大流最小割定理” 我们先来着手解决第一个问题：无向图转化成有向图。 …

题面 只能看看题面，数据是错的。 就是求一张图的所有点双连通分量，将它们内部排序再外部排序数出来，关于点双连通分量没什么好讲的，网上各种博客都写烂了。还是直接上代码吧。 [crayon-67eae5ff23b88393456884/]

题目描述 在一个地区中有 n 个村庄，编号为 1, 2, ..., n。有 n – 1 条道路连接着这些村 庄，每条道路刚好连接两个村庄，从任何一个村庄，都可以通过这些道路到达其 他任一个村庄。每条道路的长度均为 1 个单位。 为保证该地区的安全，巡警车每天要到所有的道路上巡逻。警察局设在编号 为 1 的村庄里，每天巡警车总是从警察局出发，最终又回…

样例输入 [crayon-67eae5ff23e75364866793/] 样例输出 [crayon-67eae5ff23e7a900847679/] 题解 算法分析摘自《2013全国信息学奥林匹克年鉴》 算法分析 这道题主要考察同学们对最短路算法的理解。（我考试的时候怎么没看出来orz） 本题是一个很典型的最短路模型的题目。 假设我们把棋盘的局面…

题目 题目描述 A国有n座城市，编号从1到n，城市之间有m条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。 输入输出格式 输入格式： 第一行有两个用一个空格隔开的整数n,m表示A国有n座城市和m条道路。 接下来m行每行3个整数 x, y, z每两个整数之…

题目 题目描述 无向连通图G 有n 个点，n – 1 条边。点从1 到n 依次编号，编号为 i 的点的权值为W i ，每条边的长度均为1 。图上两点( u , v ) 的距离定义为u 点到v 点的最短距离。对于图G 上的点对( u, v) ，若它们的距离为2 ，则它们之间会产生Wu ×Wv 的联合权值。 请问图G 上所有可产生联合权值的有序点对中，…

题目 题目描述 C 国有n 个大城市和m 条道路，每条道路连接这n 个城市中的某两个城市。任意两个 城市之间最多只有一条道路直接相连。这m 条道路中有一部分为单向通行的道路，一部分 为双向通行的道路，双向通行的道路在统计条数时也计为1 条。 C 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价 格不一定相同。但是，同一种商…