网络流求助
  • 板块学术版
  • 楼主WD2c0mP
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/3/4 15:37
  • 上次更新2023/10/23 23:07:50
查看原帖
网络流求助
780641
WD2c0mP楼主2023/3/4 15:37

P2740 USACO4.2草地排水Drainage DitchesP3376 【模板】网络最大流好像没啥区别,可为啥3376的AC代码交到2740就变成这样了?

alt xxx

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t,u,v;
typedef long long ll;
ll w,ans,dis[500010];
int tot = 1,vis[500010],pre[500010],head[500010],flag[2510][2510];

struct node {
	int to,net;
	ll val;
} e[500010];
inline void add(int u,int v,ll w) {
	e[++tot].to = v;
	e[tot].val = w;
	e[tot].net = head[u];
	head[u] = tot;
	
	e[++tot].to = u;
	e[tot].val = 0;
	e[tot].net = head[v];
	head[v] = tot;
}

inline int bfs() {
	for (int i = 1;i <= n;i ++) vis[i] = 0;
	queue<int>q;
	q.push(s);
	vis[s] = 1;
	dis[s] = 1919810114;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = head[x];i;i = e[i].net) {
			if (e[i].val == 0) continue;
			int v = e[i].to;
			if (vis[v]) continue;
			dis[v] = min(dis[x],e[i].val);
			pre[v] = i;
			q.push(v);
			vis[v] = 1;
			if (v == t) return 1;
		}
	}
	return 0;
}

inline void update() {
	int x = t;
	while (x != s) {
		int v = pre[x];
		e[v].val -= dis[t];
		e[v ^ 1].val += dis[t];
		x = e[v ^ 1].to;
	}
	ans += dis[t];
}
int main(){
	cin >> n >> m >> s >> t;
	for (int i = 1;i <= m;i ++) {
		cin >> u >> v >> w;
		if (flag[u][v] == 0) {
			add(u,v,w);
			flag[u][v] = tot;
		} else {
			e[flag[u][v] - 1].val += w; 
		}
	}
	while (bfs() != 0) update();
	cout << ans << endl;
	return 0;
} 
2023/3/4 15:37
加载中...