P4542 [ZJOI2011] 营救皮卡丘
注意到什么叫
两 面 包 夹 芝 士
这个是 最优解
这个是 最劣解
这究竟是怎么一回事呢？请看下文
挺有趣的这道题，我们先来
分析一下限制
最基础的就是 每个点都需要经过 这一点，并且要求 总路程最小
很容易想到的就是 路径覆盖问题，进而可以尝试 费用流 去求解
在有向图 \(G\) 中，设 \(P\) 是一个 简单路（顶点不相交）集合
如果 \(G\) 中的 每个顶点 都在 \(P\) 中的 一条路上，那么 \(P\) 就是 \(G\) 的 一个路径覆盖
而 路径覆盖问题 就是 在 \(G\) 中 求得特殊的的路径覆盖 \(P\) 的问题
例如 最小路径覆盖问题，注意到这里的最小不是指 最小权值，而是 路径条数最少
这类问题的基本思路就是 将每个点拆成两个点，建立 二分图
在原图上 有边的点对应的二分图，左右 / 右左 连边，求解（最小费用）最大匹配
难就难在这题有两个 特殊限制，第一个是 有 \(k\) 个人，也就是 最多同时走 \(k\) 路
但只是这个还是好解决的，我们可以限制 源点 到 起点（对应的左部点）的流量
但是注意到另一个条件，即 到达点 \(K\) 时，必须已经经过过点 \(1 \sim K - 1\)
当时我就感觉 有点难搞啊，想了一会儿，考虑到这种 条件递进 的关系
于是有了 分层图 的想法（埋下伏笔）
最劣解是怎么来的
这种想法 确实非常直观，只是...需要 大大大力卡常 + 代码复杂
有一种 \(ZJOI \to Ynoi\) 的美
我们可以直接 暴力把点分成 \(N\) 层，每层每个点向下一层对应点连单向边（保证不会走回来）
注意到 每个点必须经过一次，而且得 按顺序经过
于是我们可以对 第 \(i\) 个点从第 \(i\) 层连向 \(i + 1\) 的边 做一个 下界流量为 \(1\) 的限制
这里 可以直接用 上下界网络流 的套路
也可以 \(u \to v\) 连一条 容量 \(1\)，费用 \(- \inf\) 的边，连一条 容量 \(\inf\)，费用 \(0\) 的边
那么求解最小费用时，显然 费用 \(-\inf\) 的边会被走到，最后 总费用 加上 \(N\) 个 \(\inf\) 即可
而其他边 不做限制，此时我们就已经保证 到第 \(i\) 层时，必然经过 \(1 \sim i - 1\) 的点
之后再来考虑 原图上的边，我们钦定原图有边 \((u, v)\)，\(u < v\)
于是我们显然可以在每一层 层内连接 \(u \to v\) 的边
而由于 \(v > u\)，为了防止破坏条件，我们需要保证 \(v\) 被炸掉之后 才能 往 比 \(v\) 小的点走
也就是在第 \(v\) 层之后，我们才连接 \(v \to u\) 的边
否则可能先炸掉 \(v\) 再炸掉 \(u\) 费用更少，但显然不合题意
虽然说这里可以在 第 \(i\) 层 就直接跳到 后面的点 \(j ~ (j > i)\)
但由于我们保证在 第 \(j\) 层之前，\(j\) 不能 “往回跳” 到 比 \(j\) 小的点
故而这种情况实际上相当于 一个人在第 \(i\) 个点，决定了去炸 \(j\)（以及后面的点）
但是其 不会途径 \(j\) 去炸 \(1 \sim j - 1\) 中的点
所以只需要等待其他人把 \(1 \sim j - 1\) 炸完再动即可，没有破坏条件
这里附赠一个样例，手玩一下有助于理解上面这段抽象的东西
5 7 2 0 1 100 1 2 3 0 3 1 3 2 1 2 4 2 3 4 100 2 5 1 Ans = 108
最后把第 \(N\) 层的 每个点连向汇点 \(T\)，大功告成
交上去，你不得不承认这玩意儿是对的，但是 \(TLE + MLE ~ 70 ~ pts\)
于是开始了 漫长的卡常
\(2024.03.07 ~~ 21:47 \to 70 ~ pts\)
发现 值域很小，于是把 long long改成 int，快了一些，不 \(MLE\) 了
\(2024.03.08 ~~ 11:12 \to 80 ~ pts\)
发现在前 \(i\) 层时，每层建一组 “向后走” 的边 十分浪费，实质上一共 只需要一组，省一半边
\(2024.03.08 ~~ 12:07 \to 90 ~ pts\)
注意到如果存在点 \(A, B, C\)，满足 \(A < B < C\) 且 \(Dis (A, B) + Dis (B, C) < Dis (A, C)\)
那么边 \((A, C)\) 可以松弛，于是用 \(Bellman-Ford\) 遍历所有可以松弛的边
\(2024.03.08 ~~ 12:27 \to AC\)
发现上文中的边 \((A, C)\) 其实 完全没用，于是在建分层图的时候可以 忽略这些边
总算过了...
然后一看提交记录... 最劣解，主要是这样建图 边数的级别 是 \(O(N M)\)，或说 \(O(N ^ 3)\)
即是砍掉了很多，在最终 \(AC\) 的版本上，最大的点还是会建出 \(742233\) 条边，十分喃伻
仔细想想，发现 点数 / 边数上可以少乘个 \(N\)... 这里先给个 劣质的代码
#include <bits/stdc++.h>
using namespace std;
namespace MCMF {
const int MAXN = 50005;
const int MAXM = 20000;
const int INF = 1e5; // Don't Be Too Large
struct Edge {
int u, v, nxt, f, w;
} E[MAXM * 38];
int H[MAXN], tot = 1;
inline void Add_Edge (const int u, const int v, const int f, const int w) {
E[++ tot] = {u, v, H[u], f, + w}, H[u] = tot;
E[++ tot] = {v, u, H[v], 0, - w}, H[v] = tot;
}
int Pre[MAXN];
int fa[MAXN], fe[MAXN], Cir[MAXN], Tag[MAXN];
int Now = 0, S = 31451, T = 49198;
inline void Init_ZCT (const int x, const int e, int Nod = 1) {
fe[x] = e, fa[x] = E[e].u, Tag[x] = Nod;
for (int i = H[x]; i; i = E[i].nxt)
if (Tag[E[i].v] != Nod && E[i].f) Init_ZCT (E[i].v, i, Nod);
}
inline int Sum (const int x) {
if (Tag[x] == Now) return Pre[x];
Tag[x] = Now, Pre[x] = Sum (fa[x]) + E[fe[x]].w;
return Pre[x];
}
inline int Push_Flow (const int x) {
int rt = E[x].u, lca = E[x].v, Cnt = 0, Del = 0, P = 2;
++ Now;
while (rt) Tag[rt] = Now, rt = fa[rt];
while (Tag[lca] != Now) Tag[lca] = Now, lca = fa[lca];
int F = E[x].f, Cost = 0;
for (int u = E[x].u; u != lca; u = fa[u]) {
Cir[++ Cnt] = fe[u];
if (F > E[fe[u]].f)
F = E[fe[u]].f, Del = u, P = 0;
}
for (int u = E[x].v; u != lca; u = fa[u]) {
Cir[++ Cnt] = fe[u] ^ 1;
if (F > E[fe[u] ^ 1].f)
F = E[fe[u] ^ 1].f, Del = u, P = 1;
}
Cir[++ Cnt] = x;
for (int i = 1; i <= Cnt; ++ i)
Cost += F * E[Cir[i]].w, E[Cir[i]].f -= F, E[Cir[i] ^ 1].f += F;
if (P == 2) return Cost;
int u = E[x].u, v = E[x].v;
if (P == 1) swap (u, v);
int Lste = x ^ P, Lstu = v, Tmp;
while (Lstu != Del) {
Lste ^= 1, -- Tag[u];
swap (fe[u], Lste);
Tmp = fa[u], fa[u] = Lstu, Lstu = u, u = Tmp;
}
return Cost;
}
int MinC = 0;
inline int Simplex () {
Add_Edge (T, S, INF, - INF);
Init_ZCT (T, 0, ++ Now);
Tag[T] = ++ Now, fa[T] = 0;
bool Run = 1;
while (Run) {
Run = 0;
for (int i = 2; i <= tot; ++ i)
if (E[i].f && E[i].w + Sum (E[i].u) - Sum (E[i].v) < 0)
MinC += Push_Flow (i), Run = 1;
}
MinC += E[tot].f * INF;
return E[tot].f;
}
}
namespace Value {
using namespace MCMF;
const int MAXP = 155;
int D[MAXP][MAXP];
int N, M, K, u, v, c;
int A[MAXN];
int VS = 31455, VT = 49199;
inline int G (const int x, const int f) {
return x + f * MAXP;
}
inline void Solve () {
cin >> N >> M >> K, ++ N;
for (int i = 1; i <= N; ++ i) {
for (int j = 1; j <= i; ++ j)
Add_Edge (G (j, i - 1), G (j, i), K, 0);
Add_Edge (S, G (i, i), 1, 0), Add_Edge (G (i, i - 1), T, 1, 0);
}
memset (D, 63, sizeof D);
for (int i = 1; i <= M; ++ i) {
cin >> u >> v >> c, ++ u, ++ v;
if (u > v) swap (u, v);
D[u][v] = min (D[u][v], c);
}
for (int i = 1; i < N; ++ i)
for (int j = i + 2; j <= N; ++ j)
for (int k = i + 1; k < j; ++ k)
if (D[i][j] < 10000 && D[i][k] + D[k][j] < D[i][j])
D[i][j] = D[i][k] + D[k][j];
for (int i = 1; i < N; ++ i)
for (int j = i + 2; j <= N; ++ j)
for (int k = i + 1; k < j; ++ k)
if (D[i][j] < 10000 && D[i][k] + D[k][j] == D[i][j])
D[i][j] = 10001;
for (u = 1; u <= N; ++ u)
for (v = u; v <= N; ++ v)
if (D[u][v] < 10000) {
c = D[u][v];
Add_Edge (G (u, u - 1), G (v, v - 1), K, c);
Add_Edge (G (u, v - 1), G (v, v - 1), K, c);
for (int k = v; k <= N; ++ k)
Add_Edge (G (v, k), G (u, k), K, c), Add_Edge (G (u, k), G (v, k), K, c);
}
for (int i = 1; i <= N; ++ i) Add_Edge (G (i, N), VT, K, 0);
Add_Edge (VS, G (1, 0), K, 0), Add_Edge (VT, VS, K, 0);
int Ans = Simplex ();
cerr << tot << endl;
cerr << Ans << endl;
cout << MinC << endl;
}
}
int main () {
Value::Solve ();
return 0;
}
最优解是怎么来的
我们注意到 第三个条件 本质上就是 不要 先炸了后面的再回头炸前面的
而我们刚刚 卡常的倒数第二步 抓住了一个关键，也就是 最短路
事实上，我们可以用 \(Bellman-Ford\) 预处理出 任意两点间 不经过后面点 的 最短路径
于是我们可以 回到二分图，同一个点 拆成左右两点，连边，保证下界为 \(1\)
按照路径覆盖的套路，设 \(Dis (u, v) = c\)，我们将 \(u\) 的 右部点 与 \(v\) 的 左部点 连接，费用为 \(c\)
注意到为防止 ”回头炸前面的“，我们需要保证此处 \(u < v\)
由于前面我们已经处理出 任意两点距离，故这里实际上任意 \(u, v\) 之间均有边，与原图无关
也就是 点号较小的点对应的右部点 与 点号较大的点对应的左部点 连 单向边
这样也就不可能出现 回头 的情况
但是可能有人会有疑问，如果 需要借道前面走过的点 时，正确性会不会有问题
我们注意到此时的 一条边 实际上代表的是 \(Bellman-Ford\) 处理出来的 一条路径
这里路径是 包括了 借道的情况，比如前面给的小样例中的 最优情况
就会存在一条 \(3 \to 2 \to 4\) 的 需要借道 的路径
而反映到 二分图 中，我们预处理出的 \(3, 4\) 的 最短距离 就是 \(3\)（\(3 \to 2 \to 4\) 的长度）
于是会有 \(3\) 的右部点 连向 \(4\) 的左部点 的 一条费用为 \(3\) 的边，也就代表了这种情况
故而容易知道，正确性保证
于是直接连边做就行了，这样边数显然只有 \(O(N ^ 2)\) 的级别
在最大的点上实际建出了 \(23561\) 条边，是上一种方法的 \(\dfrac {1} {32}\) 左右，十分的快
#include <bits/stdc++.h>
using namespace std;
namespace MCMF {
const int MAXN = 50005;
const int MAXM = 20000;
const int INF = 1e5; // Don't Be Too Large
struct Edge {
int u, v, nxt, f, w;
} E[MAXM * 2];
int H[MAXN], tot = 1;
inline void Add_Edge (const int u, const int v, const int f, const int w) {
E[++ tot] = {u, v, H[u], f, + w}, H[u] = tot;
E[++ tot] = {v, u, H[v], 0, - w}, H[v] = tot;
}
int Pre[MAXN];
int fa[MAXN], fe[MAXN], Cir[MAXN], Tag[MAXN];
int Now = 0, S = 31451, T = 49198;
inline void Init_ZCT (const int x, const int e, int Nod = 1) {
fe[x] = e, fa[x] = E[e].u, Tag[x] = Nod;
for (int i = H[x]; i; i = E[i].nxt)
if (Tag[E[i].v] != Nod && E[i].f) Init_ZCT (E[i].v, i, Nod);
}
inline int Sum (const int x) {
if (Tag[x] == Now) return Pre[x];
Tag[x] = Now, Pre[x] = Sum (fa[x]) + E[fe[x]].w;
return Pre[x];
}
inline int Push_Flow (const int x) {
int rt = E[x].u, lca = E[x].v, Cnt = 0, Del = 0, P = 2;
++ Now;
while (rt) Tag[rt] = Now, rt = fa[rt];
while (Tag[lca] != Now) Tag[lca] = Now, lca = fa[lca];
int F = E[x].f, Cost = 0;
for (int u = E[x].u; u != lca; u = fa[u]) {
Cir[++ Cnt] = fe[u];
if (F > E[fe[u]].f)
F = E[fe[u]].f, Del = u, P = 0;
}
for (int u = E[x].v; u != lca; u = fa[u]) {
Cir[++ Cnt] = fe[u] ^ 1;
if (F > E[fe[u] ^ 1].f)
F = E[fe[u] ^ 1].f, Del = u, P = 1;
}
Cir[++ Cnt] = x;
for (int i = 1; i <= Cnt; ++ i)
Cost += F * E[Cir[i]].w, E[Cir[i]].f -= F, E[Cir[i] ^ 1].f += F;
if (P == 2) return Cost;
int u = E[x].u, v = E[x].v;
if (P == 1) swap (u, v);
int Lste = x ^ P, Lstu = v, Tmp;
while (Lstu != Del) {
Lste ^= 1, -- Tag[u];
swap (fe[u], Lste);
Tmp = fa[u], fa[u] = Lstu, Lstu = u, u = Tmp;
}
return Cost;
}
int MinC = 0;
inline int Simplex () {
Add_Edge (T, S, INF, - INF);
Init_ZCT (T, 0, ++ Now);
Tag[T] = ++ Now, fa[T] = 0;
bool Run = 1;
while (Run) {
Run = 0;
for (int i = 2; i <= tot; ++ i)
if (E[i].f && E[i].w + Sum (E[i].u) - Sum (E[i].v) < 0)
MinC += Push_Flow (i), Run = 1;
}
MinC += E[tot].f * INF;
return E[tot].f;
}
}
namespace Value {
using namespace MCMF;
const int MAXP = 155;
int D[MAXP][MAXP];
int N, M, K, u, v, c;
int A[MAXN];
int VS = 31455, VT = 49199;
inline int G (const int x, const int f) {
return x + f * MAXP;
}
inline void Solve () {
cin >> N >> M >> K, ++ N;
for (int i = 1; i <= N; ++ i) {
Add_Edge (G (i, 0), G(i, 1), 1, - 1e6);
Add_Edge (G (i, 0), G (i, 1), K, 0);
Add_Edge (G (i, 1), T, K, 0);
}
memset (D, 63, sizeof D);
for (int i = 1; i <= M; ++ i) {
cin >> u >> v >> c, ++ u, ++ v;
if (u > v) swap (u, v);
D[v][u] = D[u][v] = min (D[u][v], c);
}
for (int i = 1; i < N; ++ i)
for (int j = i; j <= N; ++ j)
for (int k = 1; k < j; ++ k)
if (D[i][k] + D[k][j] < D[i][j])
D[j][i] = D[i][j] = D[i][k] + D[k][j];
for (int i = 1; i < N; ++ i)
for (int j = i + 1; j <= N; ++ j)
Add_Edge (G (i, 1), G (j, 0), K, D[i][j]);
Add_Edge (S, G (1, 0), K, 0);
int Ans = Simplex ();
cerr << Ans << endl;
cout << (MinC + N * 1000000) << endl;
}
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
Value::Solve ();
return 0;
}