洛谷P2740 草地排水Drainage Ditches 题解

题目大意

最大流板子题。

解题思路

板子题。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define endl '\n'
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const int INF = 1e9;
struct {
	int to, next, val;
}edge[1010];
int n, m, s, t;
int cnt, head[1010];
int dep[1010];
int cur[1010];

void build(int u, int v, int val) {
	edge[cnt].to = v, edge[cnt].val = val;
	edge[cnt].next = head[u], head[u] = cnt++;
}

int bfs() {
	queue<int> q;
	q.push(s);
	memset(dep, -1, sizeof(dep));
	dep[s] = 0;
	while (!q.empty()) {
		int node = q.front(); q.pop();
		for (int i = head[node]; ~i; i = edge[i].next) {
			int v = edge[i].to;
			if (dep[v] == -1 && edge[i].val > 0)
				dep[v] = dep[node] + 1, q.push(v);
		}
	}
	return ~dep[t];
}

int dfs(int pos, int flow) {
	if (pos == t) return flow;
	int tmp = 0, res = 0;
	for (int& i = cur[pos]; ~i; i = edge[i].next) {
		int v = edge[i].to;
		if (dep[v] == (dep[pos] + 1) && edge[i].val > 0) {
			tmp = dfs(v, min(flow, edge[i].val));
			if (!tmp) continue;
			flow -= tmp;
			res += tmp;
			edge[i].val -= tmp;
			edge[i ^ 1].val += tmp;
			if (!flow) break;
		}
	}
	return res;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> m >> n;
	s = 1, t = n;
	cnt = 0;
	memset(head, -1, sizeof(head));
	rep(i, 1, m) {
		int u, v, w;
		cin >> u >> v >> w;
		build(u, v, w);
		build(v, u, 0);
	}
	int ans = 0;
	while (bfs()) {
		rep(i, 1, n) cur[i] = head[i];
		ans += dfs(s, INF);
	}
	cout << ans << endl;
	return 0;
}