0pts求助,悬赏一关
查看原帖
0pts求助,悬赏一关
550933
Tjaweiof楼主2023/12/27 21:22

RT,提交记录

#include <bits/stdc++.h>
using namespace std;
int fl[201], wlevel[201][201];
pair <int, int> wraw[201][201];
vector <int> raw[201], level[201];
void make(int s){
	memset(fl, 0, sizeof fl);
	for (int i = 1; i <= 200; i++){
		level[i].clear();
	}
	queue <int> q;
	q.push(s);
	while (!q.empty()){
		int u = q.front();
		q.pop();
		for (auto v : raw[u]){
			if (wraw[u][v].second && !fl[v]){
				q.push(v);
				fl[v] = fl[u] + 1;
				level[u].push_back(v);
				wlevel[u][v] = wraw[u][v].second;
			}
		}
	}
	return;
}
int dfs(int x, int t, int ans){
	if (x == t){
		return ans;
	}
	if (fl[x] >= fl[t]){
		return 0;
	}
	int res = 0;
	for (auto u : level[x]){
		if (wlevel[x][u]){
			int d = dfs(u, t, min(ans, wlevel[x][u]));
			res += d;
			wraw[x][u].second -= d;
		}
	}
	return res;
}
int dinic(int s, int t){
	int ans = 0;
	while (true){
		make(s);
		if (!fl[t]){
			break;
		}
		ans += dfs(s, t, 2147483647);
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m, s, t, u, v, w;
	cin >> n >> m >> s >> t;
	for (int i = 1; i <= m; i++){
		cin >> u >> v >> w;
		raw[u].push_back(v);
		wraw[u][v] = {w, w};
	}
	cout << dinic(s, t);
	return 0;
}

2023/12/27 21:22
加载中...