[BalticOI 2008]黑手党 - 洛谷 发现就是考虑对多少个点打标记使得 $S \to T$ 的任意一条路径都是有标记的点。 本质就是割掉若干个点使得 $S,T$ 不连通。 每个点有权值也是没有关系的，所以直接拆点跑最小割就行了。 注意： 如果要输出方案的话，我们考虑遍历 $S$ 可以到达的点集，对于每个点打标记，如果说存在一条边使得两边的点是在不同的集合，那么这条边就是被割掉的。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123#include <bits/stdc++.h>using names ...

[USACO05JAN]Muddy Fields G 本质上就是求每个点的最小点覆盖，考虑到一个木板可以覆盖横着或者竖着，可以考虑对于可以被同一个木板覆盖的位置可以缩点成同一个。 因为能被同一个木板覆盖肯定比分成两块木板覆盖优。 对于行和列分别进行操作，我们考虑对于图上每个点对于行列的限制是什么。 如果这个行被选择了那么对应的列是不能覆盖到当前位置的。 这个本质就是一个匹配，我们求的是最少要多个点能将全部的行和列被覆盖，本质上就是最大独立集，也就是二分图的最大匹配。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899#include <bits/stdc++.h>using namespace std;namespace Legendgod
...

[ZJOI2007] 矩阵游戏 - 洛谷 不能说我会做，只能说这个题目是我根据套路猜出来的。 众所周知我们会考虑将行和列拆开进行计算，我们考虑这个题目，最终的要求就是第 $(i, i)$ 位置是黑色的，也就是第 $i$ 行和第 $i$ 列恰好有一个黑色的匹配。 那么对于一个最终状态就是有 $n$ 个匹配，我们猜测只要有 $n$ 个匹配的都是合法的状态。 考虑左边是行右边是列，这个就是一个二分图，对于这个二分图考虑进行交换某两行的操作，相对行不变可以发现对应的列进行了交换。 那么对于最终的答案我们可以通过交换某两行达到二分图上列的交换，同理行也是可以进行交换。 根据题目交换明显是可逆的，所以这个就是充要条件。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include <bits/stdc++.h>u ...

之前不是很懂我们现在再来了解一下。 三元环首先考虑我们暴力就是枚举一个点之后枚举边看一下是否相连。 那么我们可以考虑枚举一条边 $(u, v)$ 再枚举 $v$ 的出边看一下是否能连接到 $u$，我们只要预先对于 $u$ 的出边打标记就可以了，复杂度是 $O(m ^ 2)$ 的。 但是事实上，三元环是没有方向的，甚至于对于三元环 $(a, b, c)$ 其任意的排列都是同一个三元环。 所以我们考虑对于边能否进行定向，考虑进行根号分治，让每个点的度数尽量小。所以我们让出边少的连接到出边多的点上。 我们还是枚举点，最外层的循环就是 $O(m)$，考虑如果当前的点度数为 $d$，其出边肯定是到比 $d$ 大的点上，最多是 $\frac{m}{d}$ 。 对于度数 $< \sqrt m$ 的点，其出边可以到达 $O(\sqrt m)$ 最多有 $O(m)$ 个。 对于度数 $> \sqrt m$ 的点，其点的个数总共只有 $\sqrt m$ 个。 所以综上复杂度是 $O(m \sqrt m)$。 1234567891011121314151617for(int i = ...

fe45d12ef140a30fdc0b661d0183268497364965149bb64f701b0a9e7f041d60ec8c084ec5ac579309d23eb390b2804b8a0efebc658d7791914eb7f24782ab4a3926a8bea64f4c6a908835726bfbda5141540ca06db4da19435d8bbf5386905224847cd8eb9cee49701ffba963b3c291f7c32ac42c5a87515b437e08ab3c66a797a601e004d39e965f468768b9f3441e61e07f95c33bec822c352662400d30ea4f6c57d8d4ed64cca54fbc7a72ec762ce170e6c5968be88c07865e35eb5a452ceefc8f081eda12f12c33793d4932b3585372c43d74afbb7ffe1107bc2e36a58d26772f765e454c1da75c0b95b7523f8da826ded8ff579902d ...

【清华集训2014】玄学 - 题目 - Universal Online Judge (uoj.ac) 首先暴力很明显，要么是模拟，要么直接树套树来搞。 考虑我们必须要维护时间轴，我们考虑对于区间能否进行一些操作。 考虑区间 $[l, r]$ 我们将其考虑一个位置 $pos$ 能取到什么，因为该操作在 $[1, l-1], [l, r], [r+1,n]$ 的贡献本质是一样的，我们考虑将区间的右端点作为代表点，查询的时候直接二分一个最接近的右端点即可。 这样我们发现我们只需要在叶子节点进行上述操作，但是区间查询呢？ 我们考虑二进制分组的思想，考虑对于两个时间 $a, b, a < b$ 如果说当前满足 $a$ 肯定满足 $b$，我们考虑通过这种情况进行归并即可。 插入的复杂度是 $O(\log n)$ 的，查询是 $O(\log^2 n)$ 的。 话说之后还要学习一下二进制分组。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354 ...

考虑题目要求我们求： $$R(v) = \sum_{s \ne v \ne t} \frac{a_sa_t sd_{s, t}(v)}{sd(s, t)}$$ 考虑将上面的东西拆掉得到： $$R(v) = \sum_{s \ne v \ne t} \frac{a_sa_tsd(s, v)sd(v, t)}{sd(s, t)}$$ 考虑枚举开始点 $s$ 可以得到关于 $s$ 的式子： $$R(v) = \sum_{s} a_s \sum_{s \ne v \ne t} \frac{a_tsd(s,v)sd(v, t)}{sd(s, t)}$$ 发现 $n$ 事实上可以让我们跑一遍全源最短路，那么本质上每一条最短路的宽度都是可以处理出来的。 那么我们考虑从后向前进行递推，那么我们的 $t$ 就是结束位置，显然最短路构成的肯定是一个 $DAG$。 设 $f(v) = \sum_t \frac{a_t sd(v, t)}{sd(s,t)}$，剩下的 $sd(s, v)$ 考虑在计算答案的时候乘上。 那么 $f$ 的转移比较显然，考虑加入一个点的时候肯定 ...

P1186 玛丽卡 - 洛谷 容易想到一个很明显的做法，就是考虑随便找出一条最短路，之后考虑删除掉任意一条边，再进行计算，答案取最大值。 但是这个复杂度明显是有问题的，我们考虑这个过程我们在干什么。 本质上就是对一条路径进行更新，或者说考虑对于 $A\to B \to C \to D \to E$ 的路径，我们删除掉 $(B, C)$，让路径变成 $A \to B \to X \to Y \to C \to D \to E$，这样更新。 我们思考，我们本质在做的就是在删掉一条边的时候，尝试求次短路，那么我们可以考虑对于每条不是最短路里的边分别进行更新，考虑求出从 $1 \to n$ 和 $n \to 1$ 的两个数组分别为 $d_1, d_n$ 那么我们可以通过 $d_1 + d_n + w$ 进行更新一段路径。 对于我们当前找到的点对 $(u, v)$ 我们考虑其最优的肯定是通过最短路算法得出的路径，我们设 $pre(i)$ 表示点 $i$ 在最短路算法中得到的前驱，那么我们 $(u, v)$ 进行的更新本质上就是对于 $u, v$ 分别考虑，一直跳 $\tt pre$ 直到和最短路 ...