本来以为自己对网络流理解足够深刻了，做了这个题才发现自己Too Naive……看懂题解都用了好久……明明只是套上了一个Floyd……
明天再做一遍。
题意
$k$ 个人从 $0$ 号点到 $n$ 号点，可以分头行动，但是规定：任何一人要到达 $k$ 点，必须至少有一个人到过 $k-1$ 点，求至少一个人到达 $n$ 号点时，所有人走过的路径长度和的最小值。
思路
看了好久题解……
看题目有点像DAG路径覆盖，然而给出的并不是DAG。考虑到编号限制，我们用编号定向，就变成DAG了。然而这就完了吗？
并没有。因为按照编号定向并不能满足“到达 $k$ 点之前， $0 \sim k-1$ 都到达过”。
考虑Floyd的动态规划本质。$f(k, i, j)$ 表示经过了前 $k$ 个点中转的 $i \rightarrow j$ 最短路长度。
考虑稍微修改一下转移：用 $f(k-1, i, j)$ 更新 $f(k, i, j)$ 时，必须满足 $k \le i$ 或者 $k \le j$ （想一想，为什么不是“且”）。
这样找出每对顶点之间的最短路之后，我们让每个人走 floyd 最短路（不一定是边，可以是路径），即为符合要求的答案。具体来说，我们把每个 floyd 最短路径抽象为新图中一条有向边，而且满足从编号小的连向编号大的。注意 0 可以被多个路径覆盖。用费用流求出最小路径覆盖即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500, MAXM = 40000, INF = 0x3f3f3f3f;
struct Edge {
int u, v, flow, cap, cost, next;
};
int e_ptr = 1, n, m, k, s, t, head[MAXN+10], G[MAXN+10][MAXN+10]; Edge E[(MAXM+10)<<1];
void addedge(int u, int v, int cap, int cost) {
E[++e_ptr] = (Edge) { u, v, 0, cap, cost, head[u] }; head[u] = e_ptr;
E[++e_ptr] = (Edge) { v, u, 0, 0, -cost, head[v] }; head[v] = e_ptr;
}
int maxflow, mincost, vis[MAXN+10], inq[MAXN+10], dist[MAXN+10];
bool spfa() {
queue<int> Q;
memset(dist, 0x3f, sizeof(dist));
Q.push(t); dist[t] = 0; inq[t] = true;
while(!Q.empty()) {
int u = Q.front(); Q.pop(); inq[u] = false;
for(int j=head[u]; j; j=E[j].next) {
int v = E[j].v, f = E[j^1].flow, c = E[j^1].cap, len = E[j^1].cost;
if(f < c && dist[v] > dist[u] + len) {
dist[v] = dist[u] + len;
if(!inq[v]) {
inq[v] = true; Q.push(v);
}
}
}
}
return dist[s] != INF;
}
int dfs(int u, int flow) {
if(u == t || flow == 0) return flow;
vis[u] = true;
int res = flow;
for(int j=head[u]; j; j=E[j].next) {
int v = E[j].v, f = E[j].flow, c = E[j].cap, len = E[j].cost;
if(f < c && !vis[v] && dist[v] == dist[u] - len) {
int aug = dfs(v, min(res, c-f));
E[j].flow += aug, E[j^1].flow -= aug;
res -= aug;
if(res == 0) break;
}
}
return flow - res;
}
void zkw() {
int curflow = 0;
while(spfa()) {
while(memset(vis, 0, sizeof(vis)), curflow = dfs(s, INF))
maxflow += curflow, mincost += dist[s] * curflow;
}
}
void init() {
int u, v, c;
scanf("%d%d%d", &n, &m, &k);
memset(G, 0x3f, sizeof(G));
for(int i = 1; i <= m; i++) {
scanf("%d%d%d", &u, &v, &c);
if(G[u][v] > c)
G[u][v] = G[v][u] = c;
}
for(int i = 0; i <= n; i++)
if(G[i][i] > 0) G[i][i] = 0;
for(int k = 0; k <= n; k++)
for(int i = 0; i <= n; i++)
for(int j = 0; j <= n; j++)
if(k <= i || k <= j)
G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
s = MAXN-1, t = MAXN;
addedge(s, 0, k, 0), addedge(n+1 + 0, t, k, 0);
for(int i = 1; i <= n; i++)
addedge(s, i, 1, 0), addedge(n+1 + i, t, 1, 0);
for(int i = 0; i <= n; i++)
for(int j = i+1; j <= n; j++)
if(G[i][j] != INF)
addedge(i, n+1 + j, INF, G[i][j]);
}
void work() {
zkw();
cout << mincost;
}
int main() {
init(); work();
return 0;
}
