自动搬运

查看原文

来自洛谷，原作者为

	WilliamFranklin 致敬钱学森

搬运于2025-08-24 21:27:47，当前版本为作者最后更新于2023-07-11 23:18:52，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这道题较水，就是一个二分+最大流

主要思路

看到求这种最大最小值的，第一直觉就是——二分。

简单证明一下，发现的确可以。

然后根据之前做题的经验，把边权小于等于 $mid$ 的边的边权改为 $1$，大于的改为 $0$。

设源点为 $1$，汇点为 $N$，将无向图变为有向图（就是无向图中的每一条边都建正反两边），然后每次在二分时判断一下新建好的这个图中的最大流是否大于 $T$ 即可。

但是，这里有一个问题：在题目中，要求一条路只能走一次，但在我们新建的有向图中，无向图中的边都已转化成两条边，所以相当于每一条路都有可能走两边。

其实我们不用担心，因为在网络流中，正向流一次，再反向流一次后，就相当于没流，抵消了。

进一步，我们发现，在代码上有一个空间上的小优化：在建残余网络时，我们还需要原网络中的每一条边再建一个正边和反边。也就是说题目中无向图的每一条边对应到我们的残余网络中，都有 $4$ 条边。所以为了节省一下空间，我们可以将方向相同的两条边合并。

额。。。也许我说的不是很清楚，具体看代码吧。。。

AC Code

// 《 肥 肠 煎 蛋 》
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <sstream>
#include <cstdio>
#include <queue>

using namespace std;

const int N = 205, M = 80005;

int h[N], e[M], ne[M], w[M], f[M], idx;
int n, m, S, T, t;
int d[N], cur[N];
bool vis[N];

void add(int a, int b, int c) {
	e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
	e[idx] = a, ne[idx] = h[b], w[idx] = c, h[b] = idx++;
}

bool bfs() {
	memset(vis, 0, sizeof(vis));
	memset(d, -1, sizeof(d)); 
	
	queue<int> q;
	
	q.push(S);
	d[S] = 0;
	vis[S] = 1;
	cur[S] = h[S];
	
	while (q.size()) {
		int t = q.front();
		
		q.pop();
		
		for (int i = h[t]; ~i; i = ne[i]) {
			int j = e[i];
			
			if (!vis[j] && f[i]) {
				vis[j] = 1;
				d[j] = d[t] + 1;
				cur[j] = h[j];
				
				if (j == T) return 1;
				
				q.push(j);
			}
		}
	}
	
	return 0;
}

int dfs(int u, int limit) {
	if (u == T) return limit;
	
	int flow = 0;
	for (int i = cur[u]; (~i) && flow < limit; i = ne[i]) {
		int j = e[i];
		
		cur[u] = i; 
		if (d[j] == d[u] + 1 && f[i]) {
			int k = dfs(j, min(f[i], limit - flow));
			
			if (!k) d[j] = -1;
			
			f[i] -= k;
			f[i ^ 1] += k;
			flow += k;
		}
	}
	
	return flow;
}

int dinic() {
	int r = 0, flow;
	
	while (bfs()) {
		while (flow = dfs(S, 1e9)) {
			r += flow;
		}
	}
	
	return r;
}

bool check(int x) {
	for (int i = 0; i < idx; i++) {
		if (w[i] <= x) f[i] = 1;
		else f[i] = 0;
	}
	
	return dinic() >= t;
}

int main() {
	memset(h, -1, sizeof(h));
	
	cin >> n >> m >> t;
	
	S = 1, T = n;
	for (int i = 1; i <= m; i++) {
		int a, b, c;
		
		cin >> a >> b >> c;
		
		add(a, b, c);
	}
	
	int l = 1, r = 1e6;
	
	while (l < r) {
		int mid = l + r >> 1;
		
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	
	cout << l << endl;
	
	return 0;
}

谢谢观看！