社区讨论

为什么?求答

P3376【模板】网络最大流参与者 4已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@lonovia4
此快照首次捕获于
2023/11/07 10:05
2 年前
此快照最后确认于
2023/11/07 15:07
2 年前
查看原帖
Dinic:
CPP
//
// Created by lndff on  2023.11.07
//
#include <bits/stdc++.h>
using namespace std;

#define LL long long
#define int LL

const int N = 210000;
const int M = 501000;
const LL INF = 1123451123123;
template <typename T> inline void read(T &x){
	int w = 1;x = 0;char s;
	while (!isdigit(s = getchar())) if (s == '-') w = -1;
	while (isdigit(s)) x = (x << 3) + (x << 1), x += s - '0', s = getchar();
	x *= w;
}

int n, m, s, t, tot = 1;
int temp[N], head[N], Next[M << 1], ver[M << 1];
LL d[N], w[M << 1];
LL ans;
void add(int u, int v, LL ww){
	ver[++tot] = v;
	w[tot] = ww;
	Next[tot] = head[u];
	head[u] = tot;
}

inline int bfs(){
	for (register int i = 1; i <= n; d[i] = INF, i++);
	queue<int> q;
	q.push(s);
	d[s] = 0;
	temp[s] = head[s];
	while (!q.empty()){
		int x = q.front();
		q.pop();
		for (int i = head[x]; i; i = Next[i]){
			if (w[i] > 0 && d[ver[i]] == INF){
				q.push(ver[i]);
				temp[ver[i]] = head[ver[i]];
				d[ver[i]] = d[x] + 1;
				if (ver[i] == t) return 1;
			}
		}
	}
	return 0;
}

inline int dfs(int x, LL sumflow){
	if (x == t) return sumflow;
	LL res, ret = 0;
	for (int i = temp[x]; i && sumflow; i = Next[i]){
		temp[x] = i;
		if (w[i] > 0 && (d[ver[i]] == d[x] + 1)){
			res = dfs(ver[i], min(sumflow, w[i]));
			if (!res) d[ver[i]] = INF;
			w[i] -= res;
			w[i ^ 1] += res;
			ret += res;
			sumflow -= res;
		}
	}
	return ret;
}
signed main(){
	read(n), read(m), read(s), read(t);
	LL ww;
	for (register int i = 1, u, v; i <= m; read(u), read(v), read(ww), add(u, v, ww), add(v, u, 0), i++);
	while (bfs()) {ans += dfs(s, INF);}
	return 0 * printf("%lld", ans);	
}
这样就AC了, 删掉#define int LL 就会WA三个点,其中一个甚至爆负,为什么?

回复

5 条回复,欢迎继续交流。

正在加载回复...