题解-P4542

本文章遵守知识共享协议 CC-BY-NC-SA，同步发表于洛谷题解区，转载时须在文章的任一位置附上原文链接和作者署名（rickyxrc）。推荐在我的个人博客阅读。

又一道网络流黑题，但是其实不是特别难。

题面大意

有 $K$ 个人在一个图的 $0$ 号点处，需要到达 $N$ 号点，在到达 $N$ 号点之前不能到达编号大于 $N$ 的点，$N$ 个人可以分头行动，求走过的最短路程之和。

解题思路

先讲讲为什么想到网络流吧。

首先我们不难看出以下性质：

1. $N$ 个人可以分头行动。
2. 路程之和与时间没有关系。
3. 并不是所有人都需要到达 $N$ 号点。
4. 在到达 $N$ 号点之前不能到达编号大于 $N$ 的点。

那么这个问题就可以转化成一个网络流的问题。

然后我们考虑等价转化上面的约束问题。

性质 $1,2,3$ 都和网络流的性质十分相似，我们着重考虑性质 $4$。

因为题目数据范围很小，我们可以用 Floyd 算法求解 $(i,j)$ 之间不经过 $j$ 之后的点所需的距离。

for(int k=1; k<=n; k++)
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			if(k < i || k < j) // 保证不走到后面的点
				disss[i][j] = std::min(disss[i][k] + disss[k][j],disss[i][j]);

然后呢，性质 $4$ 还有一个隐含条件：每个点都必须走到。

这个很简单，我们进行拆点，将每个点拆成 $i$ 和 $i'$，向其中连接一条 $(1,-inf)$ 和一条 $(inf,0)$ 的边，最后给答案加上 $n$ 倍的 $inf$ 即可。

for(int i=1; i<=n; i++)
	addedge(i,i+n,1,-inf_tmp),     // 保证n个点都走到
        addedge(i,i+n,inf,0),      // 允许重复走
        addedge(i+n,t,inf,0);      // 可以在任意点结束

最后再将图放进网络流里面，跑一遍最大流即可。

	for(int i=1; i<=n; i++)
		for(int j=i+1; j<=n; j++)
			if(disss[i][j] != inf)
				addedge(i+n,j,inf,disss[i][j]); // 图的信息放到网络流里面

不过有个注意事项：如果你使用了如下的建图方式来规避零点的影响，请将 $n$ 增加 $1$。（不过应该是只有我这种菜鸡才会犯的错）

for(int i=1; i<=m; i++) {
	scanf("%lld%lld%lld",&u,&v,&w);
	u++,v++;
	disss[v][u] = disss[u][v] = std::min(disss[u][v],w);
}

完整代码如下：

#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>

#define int long long

const int maxn = 6 * 150 + 7, maxm = 2 * 6 * 2e4 + 5, inf = 0x3f3f3f3f3f3f3f3fll, inf_tmp = 1000000000ll;

int n, m, tot=1, head[maxn], cur[maxn], ter[maxm], nxt[maxm], cap[maxm], cost[maxm], dis[maxn], ret, vis[maxn];

void add(int u, int v, int w, int c) {
	ter[++tot] = v, nxt[tot] = head[u], head[u] = tot, cap[tot] = w, cost[tot] = c;
}
void addedge(int u, int v, int w, int c) {
//	printf("%lld %lld %lld,%lld\n",u,v,w,c);
	add(u, v, w, c) , add(v, u, 0, -c);
}

bool spfa(int s,int t) {
	memset(dis, inf , sizeof(dis)), memcpy(cur, head, sizeof(head));
	std::queue<int> q;
	q.push(s), dis[s] = 0, vis[s] = 1;
	while(!q.empty()) {
		int fr = q.front();
		q.pop(), vis[fr] = 0;
		for(int i = head[fr] ; i ; i = nxt[i]) {
			int v = ter[i];
			if(cap[i] && dis[v] > dis[fr] + cost[i]) {
				dis[v] = dis[fr] + cost[i];
				if(!vis[v])
					q.push(v), vis[v] = 1;
			}
		}
	}
	return dis[t] != inf;
}

int dfs(int u, int t, int flow) {
	if(u == t) return flow;
	vis[u] = 1;
	int ans = 0;
	for(int &i = cur[u] ; i && ans < flow ; i = nxt[i]) {
		int v = ter[i];
		if(!vis[v] && cap[i] && dis[v] == dis[u] + cost[i]) {
			int x = dfs(v, t, std::min(cap[i], flow - ans));
			if(x) ret += x * cost[i], cap[i] -= x, cap[i^1] += x, ans += x;
		}
	}
	vis[u] = 0;
	return ans;
}

int mcmf(int s, int t) {
	int ans = 0, x;
	while (spfa(s,t)) {
		while(x = dfs(s,t,inf))
			ans += x;
	}
	return ans;
}

int u, v, w, c, s, t, disss[maxn][maxn], k;
signed main() {
	memset(disss,inf,sizeof disss);
	scanf("%lld%lld%lld",&n,&m,&k);

	n++;
	s = 2*n+1;
	t = 2*n+2;

	for(int i=1; i<=m; i++) {
		scanf("%lld%lld%lld",&u,&v,&w);
		u++,v++;
		disss[v][u] = disss[u][v] = std::min(disss[u][v],w);
	}

	for(int k=1; k<=n; k++)
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				if(k < i || k < j) // 保证不走到后面的点
					disss[i][j] = std::min(disss[i][k] + disss[k][j],disss[i][j]);

	addedge(s,1,k,0);

	for(int i=1; i<=n; i++)
		addedge(i,i+n,1,-inf_tmp),     // 保证n个点都走到
		        addedge(i,i+n,inf,0),      // 允许重复走
		        addedge(i+n,t,inf,0);      // 可以在任意点结束

	for(int i=1; i<=n; i++)
		for(int j=i+1; j<=n; j++)
			if(disss[i][j] != inf)
				addedge(i+n,j,inf,disss[i][j]); // 图的信息放到网络流里面

	int ans = mcmf(s, t);
	printf("%lld\n", ret + inf_tmp * n); // 因为流量约束时减掉了，所以这里加回来

	return 0;
}