题目链接

用最多经过\(k\)条经过\(0\)的路径覆盖所有点。

定义\(ds[i][j]\)表示从\(i\)到\(j\)不经过大于\(max(i,j)\)的点的最短路，显然可以用弗洛伊德求。

然后每个点拆成入出点，连边

源点向\(0\)的入点连流量k费用0的边，表示最多经过\(0\)K次

源点向其余每个点的入点连流量1费用0的边

每个\(i\)的入点向\(j(j>i)\)连流量1费用\(ds[i][j]\)的边

每个点出点向汇点连流量1费用0的边

最小费用即为所求。

#include <cstdio>

#include <queue>

#include <cstring>

#define INF 2147483647

using namespace std;

const int MAXN = 350;

const int MAXM = 40010;

struct Edge{

	int from, next, to, rest, cost;

}e[MAXM];

int head[MAXN], num = 1, n, m, k;

inline void Add(int from, int to, int flow, int cost){

	e[++num] = (Edge){from, head[from], to, flow, cost}; head[from] = num;

	e[++num] = (Edge){to, head[to], from, 0, -cost}; head[to] = num;

}

int s, t, a, b, c, d[MAXM], now, maxflow, mincost;

queue <int> q;

int v[MAXN], dis[MAXN], pre[MAXN], flow[MAXN], ds[MAXN][MAXN];

int re(){

	q.push(s);

	memset(dis, 127, sizeof dis);

	memset(flow, 0, sizeof flow);

	dis[s] = 0; pre[t] = 0; flow[s] = INF;

	while(q.size()){

		now = q.front(); q.pop(); v[now] = 0;

		for(int i = head[now]; i; i = e[i].next)

		   if(e[i].rest && dis[e[i].to] > dis[now] + e[i].cost){

		     dis[e[i].to] = dis[now] + e[i].cost;

		     pre[e[i].to] = i; flow[e[i].to] = min(flow[now], e[i].rest);

		     if(!v[e[i].to]) v[e[i].to] = 1, q.push(e[i].to);

		   }

	}

	return pre[t];

}

int main(){

	scanf("%d%d%d", &n, &m, &k); s = 345; t = 346;

	memset(ds, 63, sizeof ds);

	for(int i = 1; i <= m; ++i){

	   scanf("%d%d%d", &a, &b, &c);

	   ds[a][b] = ds[b][a] = min(ds[a][b], c);

    }

    for(int k = 0; k <= n; ++k)

       for(int i = 0; i <= n; ++i)

          for(int j = 0; j <= n; ++j)

             if(k < max(i, j) && ds[i][j] > ds[i][k] + ds[k][j])

               ds[i][j] = ds[i][k] + ds[k][j];

    for(int i = 0; i <= n; ++i){

    	Add(s, i, !i ? k : 1, 0);

    	Add(i + n + 1, t, 1, 0);

    	for(int j = i + 1; j <= n; ++j)

    	   Add(i, j + n + 1, 1, ds[i][j]);

    }

    while(re()){

    	now = pre[t];

    	while(now){

    		e[now].rest -= flow[t];

    		e[now ^ 1].rest += flow[t];

    		mincost += e[now].cost * flow[t];

    		now = pre[e[now].from];

    	}

    }

    printf("%d\n", mincost);

	return 0;

}