前置技能：DAG的最小路径覆盖和最小链覆盖.
算了还是写一下吧免得自己忘了.
最小路径覆盖的做法就是把每个点$i$拆成两个点$i _0,i _1$，边$(i,j)$变成$(i _0,j _1)$，然后做最大匹配，这样每条匹配边相当于原图中一条边，匹配保证了每个点最多有一条入边一条出边，答案就是原图点数-匹配数，因为你可以看成每个点先独立为一条路径，每加入一条边相当于合并两条路径.
最小链覆盖的话边可以相交，所以需要先用floyd传递闭包，其实就是对于所有点对$(i,j)$求出是否有一条链从$i$到$j$，有的话直接连一条边过去，这样两条链相交的话其中一条就可以直接跳过交点.
题目可以认为是用$k$条可相交的路径去覆盖这张图，满足一些条件，让边权和最小.
因为可相交，先考虑来一发传递闭包，因为题目要求，状态要改成$g _{i,j}$表示只经过编号不超过$\max(i,j)$的点，从$i$到$j$的最短路，然后对所有$i\lt j$，以$g _{i,j}$为权值连边.
这样题目就变成了用$k$条只在$0$号点相交的路径去覆盖这张图，然后就能够按照DAG最小路径覆盖来建图了，需要注意的是，源点连向$0$号点的入点的边容量为$k$，因为这$k$条路径能在$0$处相交即$0$号点出去的边最多可以选$k$条. 边的费用当然就是$g _{i,j}$.
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
using namespace std;
const ele INF=1e9;
struct edge{
ele v,r,c;
edge *nxt,*rev;
}ep[10000000],*ecnt;
ele n,m,K,g[maxn][maxn],d[maxn];
bool vis[maxn];
edge *h[maxn],*cur[maxn];
inline void addedge1(ele u,ele v,ele r,ele c){
edge *p=ecnt++;
p->v=v; p->r=r; p->c=c; p->nxt=h[u]; p->rev=ep+((ecnt-1-ep)^1);
h[u]=p;
}
inline void addedge(ele u,ele v,ele r,ele c){
addedge1(u,v,r,c); addedge1(v,u,0,-c);
}
inline bool spfa(ele s,ele t){
static queue<ele> Q;
for (int i=0; i<n*2+4; ++i) d[i]=INF;
d[s]=0;
Q.push(s);
while (!Q.empty()){
ele k=Q.front(); Q.pop();
for (edge *j=h[k]; j; j=j->nxt)
if (j->r && d[k]+j->c<d[j->v]){
d[j->v]=d[k]+j->c;
Q.push(j->v);
}
}
return d[t]<INF;
}
pair<ele,ele> dfs(ele i,ele t,ele p){
if (!p || i==t) return make_pair(0,p);
ele ans=0,ans1=0;
vis[i]=true;
for (edge*&j=cur[i]; j; j=j->nxt)
if (!vis[j->v] && j->r && d[i]+j->c==d[j->v]){
pair<ele,ele>tmp =dfs(j->v,t,min(p,j->r));
if (tmp.se){
ans+=tmp.fi; ans+=j->c*tmp.se;
ans1+=tmp.se;
j->r-=tmp.se; j->rev->r+=tmp.se;
p-=tmp.se;
if (!p) break;
}
else d[j->v]=INF;
}
return make_pair(ans,ans1);
}
inline ele mincost(ele s,ele t){
ele ans=0;
while (spfa(s,t)){
memset(vis,0,sizeof(vis));
memcpy(cur,h,sizeof(h));
ans+=dfs(s,t,INF).fi;
}
return ans;
}
int main(){
scanf("%d%d%d",&n,&m,&K);
for (int i=0; i<=n; ++i)
for (int j=0; j<=n; ++j) g[i][j]=INF;
while (m--){
ele u,v,w;
scanf("%d%d%d",&u,&v,&w);
g[u][v]=g[v][u]=min(g[u][v],w);
}
for (int k=0; k<=n; ++k)
for (int i=0; i<=n; ++i)
for (int j=0; j<=n; ++j)
if (max(i,j)>=k)
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
ecnt=ep; memset(h,0,sizeof(h));
for (int i=0; i<=n; ++i)
for (int j=i+1; j<=n; ++j) addedge(2+i*2,2+j*2+1,1,g[i][j]);
addedge(0,2,K,0);
for (int i=1; i<=n; ++i) addedge(0,2+i*2,1,0);
for (int i=0; i<=n; ++i) addedge(2+i*2+1,1,1,0);
printf("%d\n",mincost(0,1));
return 0;
}