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

RT,提交记录

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

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