自动搬运

查看原文

来自洛谷，原作者为

	郑朝曦zzx 溪涧岂能留得住，终归大海作波涛。

搬运于2025-08-24 22:23:47，当前版本为作者最后更新于2022-02-19 10:03:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一 解题算法

本题所用的算法是最短路、二分答案、网络最大流。此处最短路使用 Floyd 算法，最大流使用 Dinic 算法。

二 解题方法

建图：

网络流问题中建图（未知问题已知化）很重要，那么这题应该怎么建图呢？

先分析题目，题目要求最小时间，所以肯定符合二分答案的性质。先拆点，把牛棚和雨棚拆开，对于每次二分到的时间，如果某两点之间可以在这个时间内到达，则建起一条无限流量的边。然后建一个超级源点，到每个牛棚建一条边权为牛的数量的边，最后建一个超级汇点，每个雨棚连一条边权为雨棚容量的边到汇点。

“检测”函数：

众所周知，二分答案中有一个检测函数，那么这个函数怎么写呢？

每次跑一下最大流算法，如果流量大于总牛量则返回真，否则返回假。

三 参考代码

我做这到题的时候最大流写的不太熟练，是照着题解写的（并非抄，哪里借鉴代码中我会尽量注明），所以我的代码和一些题解会比较相似。这是完整代码：

#include <cstdio>
#include <cstring>
#include <queue>
#define ll long long
#define maxn 4100
#define maxm 16000
#define inf 100000000000000000
using namespace std;
int n, m, cnt = 1, S, T;
ll ans = inf, sum;
int cow[maxn], house[maxn], head[maxn], nlast[maxn];
ll dis[maxn][maxn];
ll Min(ll x, ll y) { return x <= y ? x : y; }
struct edge
{
	int to, next;
	ll f;
}e[maxm << 3];
void add_edge(int f, int t, ll fl)
{
	e[++cnt] = (edge){t, head[f], fl};
	head[f] = cnt;
	e[++cnt] = (edge){f, head[t], 0};
	head[t] = cnt;
}
void input()
{
	scanf("%d %d", &n, &m);
	S = 2 * n + 1;
	T = 2 * n + 2;
	for (int i = 1; i <= n; ++i)
	{
		scanf("%d %d", &cow[i], &house[i]);
		sum += (ll)cow[i];
	}
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			dis[i][j] = inf;
	for (int i = 1; i <= n; ++i)
		dis[i][i] = 0;
	for (int i = 1; i <= m; ++i)
	{
		int from, to, Dis;
		scanf("%d %d %d", &from, &to, &Dis);
		dis[from][to] = Min(dis[from][to], Dis);
		dis[to][from] = Min(dis[to][from], Dis);
        //这里借鉴了题解
	}
}
void init()
{
	memset(head, 0, sizeof(head));
	memset(nlast, 0, sizeof(nlast));
	cnt = 1;
}
void Floyd()
{
	for (int k = 1; k <= n; ++k)
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= n; ++j)
				dis[i][j] = Min(dis[i][j], dis[i][k] + dis[k][j]);
//	for (int i = 1; i <= n; ++i)
//	{
//		for (int j = 1; j <= n; ++j)
//			printf("%lld ", dis[i][j]);
//		puts(" ");
//	}
}
int dist[maxn];
bool vis[maxn];
bool bfs()
{
	//bfs判断连通性，以及每一个点到终点的距离
	memset(dist, 0, sizeof(dist));
	memset(vis, 0, sizeof(vis));
	queue <int> q;
	vis[T] = true;
	dist[T] = 1;
	q.push(T);
	while (!q.empty())
	{
		const int now = q.front();
		//printf("%d ", now);
		q.pop();
		for (int i = head[now]; i; i = e[i].next)
		{
			const int to = e[i].to;
			if (vis[to] == false && e[i ^ 1].f)
			{//如果这条边的反向边还有残量，而且这个节点没被访问过
				vis[to] = true;
				dist[to] = dist[now] + 1;
				q.push(to);
			}
		}
	}
	return vis[S];
}
ll Dinic(int x, ll f)
{
	if (x == T) return f;
	//如果这个点就是终点
	ll now = f;
	//now表示剩余流量
	for (int i = nlast[x]; i; i = e[i].next)
	{
		const int to = e[i].to;
		if (dist[to] == dist[x] - 1 && e[i].f)
		{//Dinic的增广原则为先增广较短的增广路
			const ll a = Dinic(to, Min(now, e[i].f));
			//a记录增广路上所有边的最小值
			e[i].f -= a;
			//e[i ^ 1] 为反悔边，即可以退回流量
			e[i ^ 1].f += a;
			now -= a;
			//增广出去剩余流量减少
			if (now == 0) return f;
		}
	}
	return f - now;
	//返回这条路径能增广的量
}
ll maxflow()
{
	ll now = 0;
	while (bfs())
	{
		for (int i = 1; i <= n * 2 + 2; ++i)
			nlast[i] = head[i];
		now += Dinic(S, inf);
	}
	return now;
}
bool check(ll mid)
{
	init();
	for (int i = 1; i <= n; ++i)
	{
		add_edge(S, i, cow[i]);
		add_edge(i + n, T, house[i]);
		for (int j = 1; j <= n; ++j)
		{
			if (i == j || dis[i][j] <= mid)
				add_edge(i, j + n, inf);
                //这里借鉴了题解。
		}
	}
	ll F = maxflow();
//	printf("%lld\n", F);
	return (F >= sum);
}
void search()
{
	ll l = 0, r = inf;
	while (l <= r)
	{
		ll mid = (l + r) >> 1;
		//printf("%lld %d\n", mid, check(mid));
		if (check(mid) == true)
		{
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
}
void output()
{
	if (ans == inf || ans == 0) printf("-1\n");
	else printf("%lld", ans);
}
int main()
{
	input();
	Floyd();
	search();
	output();
	return 0;
}

管理员，求通过。