萌新求助网络流EK算法
查看原帖
萌新求助网络流EK算法
117662
那一条变阻器楼主2020/7/9 15:04

WA了8,9,10点,查了好久都找不到qnq

#include <bits/stdc++.h>
using namespace std;
long long n , m , s , t , ans;
long long pre[2010] , dis[2010][2010] , vis[2010];
vector<long long> e[200010];
bool bfs(){
	memset(vis , 0 , sizeof(vis));
	queue<long long> q;
	vis[s] = 1;
	q.push(s);
	while(!q.empty()){
		long long x = q.front();
		q.pop();
		for(long long i = 0; i < e[x].size(); i++){
			long long nx = e[x][i];
			if(dis[x][nx] && !vis[nx]){
				pre[nx] = x;
				q.push(nx);
				vis[nx] = 1;
				if(nx == t) return 1;
			}
		}
	}
	return 0;
}
void update(){
	long long x = t;
	long long minn = 0x3ffffffff;
	for(long long i = t; i != s; i = pre[i]) minn = min(minn , dis[pre[i]][i]);
	while(x != s){
		long long px = pre[x];
		dis[x][px] += minn;
		dis[px][x] -= minn;
		x = px;
	}
	ans += minn;
}
int main(){
	cin >> n >> m >> s >> t;
	for(long long i = 1; i <= m; i++){
		long long x , y;
		long long z;
		cin >> x >> y >> z;
		e[x].push_back(y);
		dis[x][y] = z;
		e[y].push_back(x);
	}
	while(bfs()) update();
	cout << ans;
	return 0;
}
2020/7/9 15:04
加载中...