字符串
P3538 [POI2012]OKR-A Horrible Poem
给定字符串，多次询问其子串的最小循环节长度。
由于循环节长度 \(len\) 一定是子串长度的约数，我们可以不断试除 \(len\) 的最小质因子，并判断是否合法，更新 \(ans\) 的最小值。线性筛 预处理所有数（\(\le5\times10^5\)）的最小质因子；判断是否是循环节可以用 哈希，若 \(hash(l,r-len+1)=hash(l+len-1,r)\) 则 \(len\) 为循环节。
最短路
P2901 [USACO08MAR]Cow Jogging G
有很多下坡道路 \((x,y,d)\)，若 \(x>y\) 则是 \(x\) 通向 \(y\)。求 \(n\) 到 \(1\) 的前 \(k\) 短的路径长度。\(1\le n\le10^3\)，\(1\le m\le10^4\)，\(1\le k\le100\)。
题意告诉我们，这张图是一个 DAG，并且对于有向边 \((u,v)\) 一定满足 \(u>v\)。为了方便，我们建出反图，答案不变。
考虑在图上 DP，设 \(f(u,i)\) 表示从 \(1\) 出发到 \(u\) 第 \(i\) 短的路径长度，对于一条边 \((u,v,w)\)，将 \(f(u)\) 的每一项加上 \(w\) 并添加到 \(f(v)\) 中。由于 \(f(u),f(v)\) 从小到大有序，我们采用归并排序。由于 \(u<v\)，我们只要从小到大枚举节点编号即可满足无后效性。时间复杂度 \(O(mk)\)。
关于归并排序，C++ 中有一个函数 std :: merge(firstIt1, lastIt1, firstIt2, lastIt2, resIt, cmp) 可以方便地实现。cmp 参数可以省略。效果是把两个已经排好序的数组归并到 resIt 中。
P1522 [USACO2.4] 牛的旅行 Cow Tours
平面上若干节点，节点间有连边，形成若干连通块，边的长度为欧几里得距离。一个连通块的 直径 是指其中两两节点之间的最短路长度最大值。现在要在两个 属于不同连通块 的节点间添加一条边，使得 新形成的大连通块的 直径尽可能小。求出这个最小值。\(1\le n\le150\)。
首先用 DFS 求出连通块。然后用 Floyd 处理出节点两两之间的最短路。
枚举不连通的点对 \((x,y)\)，加边。设 \(maxd(x)\) 表示在连通块内其他点与 \(x\) 的最短路长度最大值。显然如果这条新加的边 \((x,y)\) 在新连通块的直径上，那么直径长度为 \(maxd(x)+dis(x,y)+maxd(y)\)。
这道题的一个坑点在于，新连通块的直径 不一定经过新加入的边，也有可能是原来两个连通块的直径的 max 值。
另一个坑点在于，所求的 不是全局最大直径，而只是新连通块的直径。
针对两个坑点的 Hack 数据。
P3489 [POI2009]WIE-Hexer
有 \(n\) 个村庄，\(m\) 条双向道路，\(p\) 种怪物，\(k\) 个铁匠，每个铁匠会居住在一个村庄里，你到了那个村庄后可以让他给你打造剑，每个铁匠打造的剑都可以对付一些特定种类的怪物。
每条道路上都可能出现一些特定种类的怪物，每条道路都有一个通过所需要的时间，现在要从 \(1\) 走到 \(n\)，初始的时候你没有剑，要求在经过一条道路的时候，对于任意一种可能出现在这条道路上的的怪物，你都有已经有至少一把剑可以对付他，求从 \(1\) 走到 \(n\) 的最短时间（打造剑不需要时间）。
\(1\le n\le 200\)，\(0\le m\le 3000\)，\(1\le p\le 13\)，\(0\le k\le n\)。
注意：剑 可以多次使用。注意到 \(p\) 的范围很小，考虑状态压缩，记录当前都有哪些剑。
在 Dijkstra 的过程中，想要用一条边 \((u,v)\) 进行松弛，还需要满足当前在 \(u\) 拥有剑的状态足以通过这条边。
P1948 [USACO08JAN]Telephone Lines S
有 \(n\) 个互不连通的点，其中有 \(p\) 对点 \((a_i,b_i)\) 可以花费 \(l_i\) 连一条无向边。有 \(k\) 次机会可以 免费连边。连边的费用为所有边花费的 最大值。问要使 \(1\) 和 \(n\) 连通，最小费用为多少。\(1\le n\le1000\)，\(1\le p\le10000\)，\(1\le l_i\le10^6\)。
二分答案 \(x\)，将题意转化一下：除了免费的边，只使用费用不超过 \(x\) 的边，能否使 \(1\) 和 \(n\) 连通。
再转化一下：从 \(1\) 到 \(n\) 的所有路径中，费用超过 \(x\) 的边数最少是否超过 \(k\)。
于是将边权设为 \([l_i>x]\)，Dijkstra 求最短路即可。时间复杂度 \(O(p\log n\log l_i)\)。
P3008 [USACO11JAN]Roads and Planes G
有 \(T\) 个城镇，它们之间通过 \(R\) 条道路和航线连接，道路或航线 \(i\) 的花费为 \(C_i\)。
道路是双向的，而航线是单向的；道路的花费非负，而航线的花费可能为负。
保证如果有一条航线可以从 \(A_i\) 到 \(B_i\)，那么不可能通过一些道路或航线从 \(B_i\) 回到 \(A_i\) 。
输出从起点城镇 \(S\) 到每个城镇的最少花费，无法到达输出 \(\texttt{NO PATH}\)。
\(1\le T\le25000\)，\(1\le R\le50000\)，\(|C_i|\le10000\)。
有向边不能用 Dijkstra，但有向边之间无环，所以可以把无向边缩成 SCC（即连通块）形成一个 DAG，然后拓扑排序找最短路。每个连通块内就可以 Dijkstra 了。
#include <queue>
#include <vector>
#include <cstring>
#include <iostream>
#define f(x, y, z) for (int x = (y); x <= (z); ++x)
using namespace std;
typedef pair<int, int> pii;
int constexpr N = 2.5e4 + 10, M = 1.5e5 + 10;
int constexpr INF = 0x7f7f7f7f;
int n, r, p, s;
int head[N], cnt;
struct Edge {
int to, nxt, val;
} e[M];
inline void add(int from, int to, int val) {
e[++cnt].to = to, e[cnt].nxt = head[from], e[cnt].val = val, head[from] = cnt;
return;
}
int c[N], tot;
vector<int> v[N];
void dfs(int u) {
c[u] = tot;
v[tot].push_back(u);
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (!c[v]) dfs(v);
}
return;
}
int deg[N];
queue<int> q;
priority_queue<pii> pq;
int d[N];
bool vis[N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> r >> p >> s;
f(i, 1, r) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w), add(v, u, w);
}
f(i, 1, n) if (!c[i]) ++tot, dfs(i);
f(i, 1, p) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
++deg[c[v]];
}
f(i, 1, tot) if (!deg[i]) q.push(i);
memset(d, 0x7f, sizeof d);
d[s] = 0;
while (!q.empty()) {
int t = q.front(); q.pop();
for (int i: v[t]) pq.emplace(-d[i], i);
while (!pq.empty()) {
int u = pq.top().second; pq.pop();
if (vis[u]) continue;
vis[u] = true;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to, w = e[i].val;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
if (c[u] == c[v]) pq.emplace(-d[v], v);
}
if (c[u] ^ c[v])
if (!--deg[c[v]]) q.push(c[v]);
}
}
}
f(i, 1, n)
if (d[i] > n * 10000) cout << "NO PATH\n";
else cout << d[i] << '\n';
return 0;
}
差分约束
P4878 [USACO05DEC]Layout G
FJ 有编号为 \(1,\dots,n\) 的 \(n\) 头奶牛。开始时，奶牛们 按照编号顺序 来排队。
有 \(m_1\) 对奶牛希望彼此之间的距离小于等于 \(d_{1i}\)（\(1\le i\le m_1\)）；有 \(m_2\) 对奶牛希望彼此之间的距离大于等于 \(d_{2i}\)（\(1\le i\le m_2\)）。
计算 \(1\) 号奶牛和 \(n\) 号奶牛之间的距离最大为多少。可能有多头奶牛在同一位置上。无解输出 \(\texttt{-1}\)，可以无穷远输出 \(\texttt{-2}\)。
\(2\le n\le1000\)，\(1\le m_1,m_2\le10^4\)，\(1\le d_{1i},d_{2i}\le10^6\)。
建立差分约束系统。首先判无解，从超级源点 \(0\) 向其他所有点连边，跑 SPFA 看有没有负环即可。然后再从 \(1\) 出发跑最短路。
注意：奶牛们按照编号顺序来排队，可能有多头奶牛在同一位置上。所以有一个 隐含条件 就是 \(a_i\ge a_{i-1}\)，于是从 \(i\) 到 \(i-1\) 连边。
P3275 [SCOI2011]糖果
幼儿园里有 \(N\) 个小朋友，\(\text{lxhgww}\) 老师现在想要给这些小朋友们分配糖果，并且满足小朋友们的 \(K\) 个要求。求至少需要准备多少个糖果。某个要求 \((X,A,B)\) 的意义如下：
- 如果 \(X=1\)， 表示第 \(A\) 个小朋友分到的糖果必须和第 \(B\) 个小朋友分到的糖果一样多；
- 如果 \(X=2\)， 表示第 \(A\) 个小朋友分到的糖果必须少于第 \(B\) 个小朋友分到的糖果；
- 如果 \(X=3\)， 表示第 \(A\) 个小朋友分到的糖果必须不少于第 \(B\) 个小朋友分到的糖果；
- 如果 \(X=4\)， 表示第 \(A\) 个小朋友分到的糖果必须多于第 \(B\) 个小朋友分到的糖果；
- 如果 \(X=5\)， 表示第 \(A\) 个小朋友分到的糖果必须不多于第 \(B\) 个小朋友分到的糖果。
无解输出 \(\texttt{-1}\)。\(N\leq100000\)，\(K\leq100000\)。
直接差分约束跑 SPFA 会被 Hack 数据卡掉。这道题的一个关键性质是：边权全部为 \(0\) 或 \(1\)。
首先考虑边权为 \(0\) 的边。用 Tarjan 算法进行缩点，那么一个 SCC 内的点分到的糖果一定相同，并且具体的糖果数相互独立。
然后重构图，并且加入边权为 \(1\) 的边。此时直接在形成的 DAG 上拓扑排序 DP 即可。无解情况是加入边权为 \(1\) 的边后出现环，可以记录拓扑排序过程中是否每个点都入过队，如果存在没有入过队的点说明有环。
0/1 分数规划
P3199 [HNOI2009]最小圈
带权的有向图 \(G=(V,E)\) 以及 \(w:E\rightarrow\mathbb R\)，每条边 \(e=(i,j)(i\neq j,i\in V,j\in V)\) 的权值定义为 \(w_{i,j}\)。令 \(n=|V|\)。\(c=(c_1,c_2,\cdots,c_k)\)（\(c_i\in V\)）是 \(G\) 中的一个 圈 当且仅当 \((c_i,c_{i+1})\)（\(1\le i<k\)）和 \((c_k,c_1)\) 都在 \(E\) 中，这时称 \(k\) 为圈 \(c\) 的长度。令 \(c_{k+1}=c_1\)，定义圈 \(c=(c_1,c_2,\cdots,c_k)\) 的 平均值 为 \(\mu(c)=\dfrac1k\sum\limits_{i=1}^{k} w_{c_i,c_{i+1}}\)，即 \(c\) 上所有边的权值的平均值。给定图 \(G\)，求出 \(\min\mu(c)\)。\(n\le 3000\)，\(m\le 10000\)。
考虑分数规划，设 \(\mu(c)>X\)，二分 \(X\)。对于固定的 \(X\)，有
\[\sum_{i=1}^k\left(w_{c_i,c_{i+1}}-X\right)<0. \]于是把所有边权减 \(X\)，判断是否有负环即可。采用 DFS-SPFA 可以更快地解决。（题目没有卡 SPFA，所以可以水过）
- Karp 算法，\(O(nm)\)：题解 P3199 【[HNOI2009]最小圈】 - _rqy 的博客 - 洛谷博客