题目
题目链接：https://www.luogu.com.cn/problem/P4542
皮卡丘被火箭队用邪恶的计谋抢走了！这三个坏家伙还给小智留下了赤果果的挑衅！为了皮卡丘，也为了正义，小智和他的朋友们义不容辞的踏上了营救皮卡丘的道路。
火箭队一共有(N)个据点，据点之间存在(M)条双向道路。据点分别从(1)到(N)标号。小智一行(K)人从真新镇出发，营救被困在(N)号据点的皮卡丘。为了方便起见，我们将真新镇视为(0)号据点，一开始(K)个人都在(0)号点。
由于火箭队的重重布防，要想摧毁(K)号据点，必须按照顺序先摧毁(1)到(K-1)号据点，并且，如果(K-1)号据点没有被摧毁，由于防御的连锁性，小智一行任何一个人进入据点(K)，都会被发现，并产生严重后果。因此，在(K-1)号据点被摧毁之前，任何人是不能够经过(K)号据点的。
为了简化问题，我们忽略战斗环节，小智一行任何一个人经过(K)号据点即认为(K)号据点被摧毁。被摧毁的据点依然是可以被经过的。
(K)个人是可以分头行动的，只要有任何一个人在(K-1)号据点被摧毁之后，经过(K)号据点，(K)号据点就被摧毁了。显然的，只要(N)号据点被摧毁，皮卡丘就得救了。
野外的道路是不安全的，因此小智一行希望在摧毁(N)号据点救出皮卡丘的同时，使得(K)个人所经过的道路的长度总和最少。
请你帮助小智设计一个最佳的营救方案吧！
(nleq 150,mleq 20000,kleq 10,L_ileq 10000)。
思路
我们可以把题目看作是用 (k) 条路径覆盖 (n) 个点，且要求新的一个点 (i) 被经过时，点 (i-1) 必须有人经过过的最短路径长度和。
那么我们只需要安排每一个人走哪些点（从小到大），每次只能走不超过当前节点编号的点到达下一个要到的点。这样我们一定可以调整所有人走的顺序满足要求。
考虑先用 Floyd 求出任意两个点 (i,j) 之间，只经过编号不超过 (max(i,j)) 的点的最短路。
然后考虑费用流。源点向 (0) 连一条 ((k,0)) 的边，把所有点拆成 (i_1,i_2)，从 (i_1) 向 (i_2) 连 ((1,-infty),(+infty,0)) 的边。这样我们就可以保证每一个点至少会被经过一次，而连第二条边是因为经过了一次后可以再经过任意次。最终答案加上 (n imes infty) 即可。
然后对于 (i<j) 且 (i,j) 之间有只经过编号不超过 (j) 的路径，我们从 (i_2) 向 (j_1) 连边 ((+infty,dis_{i}{j}))。最后从所有 (i_2) 向汇点连 ((1,0)) 的边。
不难发现这种模型是符合题意的。跑费用流即可。因为只有编号小的会连向大的，所以不用担心有负环。
时间复杂度 (O(nm^2))。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500,M=60010,Inf=1e9;
int n,m,t,S,T,tot=1,head[N],pre[N],dis1[N][N];
ll cost,dis[N];
bool vis[N];
struct edge
{
int next,to,flow,cost;
}e[M];
void add(int from,int to,int flow,int cost)
{
e[++tot]=(edge){head[from],to,flow,cost};
head[from]=tot;
swap(from,to);
e[++tot]=(edge){head[from],to,0,-cost};
head[from]=tot;
}
bool spfa()
{
memset(vis,0,sizeof(vis));
memset(dis,0x3f3f3f3f,sizeof(dis));
queue<int> q;
q.push(S); dis[S]=0;
while (q.size())
{
int u=q.front(); q.pop();
vis[u]=0;
for (int i=head[u];~i;i=e[i].next)
{
int v=e[i].to;
if (e[i].flow && dis[v]>dis[u]+e[i].cost)
{
dis[v]=dis[u]+e[i].cost;
pre[v]=i;
if (!vis[v])
{
q.push(v);
vis[v]=1;
}
}
}
}
return dis[T]<1e18;
}
void addflow()
{
int minf=Inf;
for (int i=T;i!=S;i=e[pre[i]^1].to)
minf=min(minf,e[pre[i]].flow);
for (int i=T;i!=S;i=e[pre[i]^1].to)
{
e[pre[i]].flow-=minf;
e[pre[i]^1].flow+=minf;
}
cost+=1LL*minf*dis[T];
}
void MCMF()
{
while (spfa())
addflow();
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d%d",&n,&m,&t);
memset(dis1,0x3f3f3f3f,sizeof(dis1));
for (int i=1,x,y,z;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
dis1[x][y]=min(dis1[x][y],z);
dis1[y][x]=min(dis1[y][x],z);
}
for (int k=0;k<=n;k++)
for (int i=k;i<=n;i++)
for (int j=k;j<=n;j++)
if (i!=j && j!=k && i!=k)
dis1[i][j]=min(dis1[i][j],dis1[i][k]+dis1[k][j]);
S=N-1; T=N-2;
add(S,0,t,0);
for (int i=0;i<=n;i++)
{
add(i,i+n+1,1,-Inf); add(i,i+n+1,Inf,0);
add(i+n+1,T,1,0);
for (int j=i+1;j<=n;j++)
if (dis1[i][j]<Inf) add(i+n+1,j,Inf,dis1[i][j]);
}
MCMF();
printf("%lld",cost+1LL*(n+1)*Inf);
return 0;
}