关于本题的迷惑行为
查看原帖
关于本题的迷惑行为
361308
Stinger楼主2021/4/9 15:05

就是我如果在EK中建了反向边就WA37,不加反向边不仅AC还跑得飞快,请问这是什么原因呢?

加反向边:

#include <cstdio>
#include <queue>
#include <cstring>
#define int long long

const int INF = 1e15;
inline int min(const int x, const int y) {return x < y ? x : y;}
struct Edge {
	int from, to, nxt, cap, flow;
} e[10005];
int head[205], a[205], p[205], tot, s, t;
inline void AddEdge(const int u, const int v, const int w) {
	e[++ tot].from = u, e[tot].to = v, e[tot].nxt = head[u], head[u] = tot;
	e[tot].flow = 0, e[tot].cap = w;
}
std::queue<int> Q;

int Edmonds_Karp()  {
	int flow(0);
	do {
		while (Q.size()) Q.pop();
		Q.push(s);
		memset(a, 0, sizeof a);
		a[s] = INF;
		while (Q.size() && !a[t]) {
			int u(Q.front());
			Q.pop();
			for (int i(head[u]); i; i = e[i].nxt) {
				const int v(e[i].to);
				if (!a[v] && e[i].cap > e[i].flow)
					a[v] = min(a[u], e[i].cap - e[i].flow), p[v] = i, Q.push(v);
			}
		}
		for (int i(t); i != s; i = e[p[i]].from)
			e[p[i]].flow += a[t], e[p[i] ^ 1].flow -= a[t];
		flow += a[t];
	} while (a[t]);
	return flow;
}

signed main() {
	int n, m;
	scanf("%lld%lld%lld%lld", &n, &m, &s, &t);
	for (int i(1); i <= m; ++ i) {
		int u, v, w;
		scanf("%lld%lld%lld", &u, &v, &w);
		AddEdge(u, v, w);
		AddEdge(v, u, 0);
	}
	printf("%lld", Edmonds_Karp());
	return 0;
}

不加:

#include <cstdio>
#include <queue>
#include <cstring>
#define int long long

const int INF = 1e15;
inline int min(const int x, const int y) {return x < y ? x : y;}
struct Edge {
	int from, to, nxt, cap;
} e[10005];
int head[205], a[205], p[205], tot, s, t;
inline void AddEdge(const int u, const int v, const int w) {
	e[++ tot].from = u, e[tot].to = v, e[tot].nxt = head[u], head[u] = tot, e[tot].cap = w;
}
std::queue<int> Q;

int Edmonds_Karp()  {
	int flow(0);
	while (true) {
		while (Q.size()) Q.pop();
		Q.push(s);
		memset(a, 0, sizeof a);
		memset(p, 0, sizeof p);
		a[s] = INF;
		while (Q.size() && !a[t]) {
			int u(Q.front());
			Q.pop();
			for (int i(head[u]); i; i = e[i].nxt) {
				const int v(e[i].to);
				if (!a[v] && e[i].cap)
					a[v] = min(a[u], e[i].cap), p[v] = i, Q.push(v);
			}
		}
		if (!a[t]) break;
		for (int i(t); i != s; i = e[p[i]].from)
			e[p[i]].cap -= a[t];
		flow += a[t];
	}
	return flow;
}

signed main() {
	int n, m;
	scanf("%lld%lld%lld%lld", &n, &m, &s, &t);
	for (int i(1); i <= m; ++ i) {
		int u, v, w;
		scanf("%lld%lld%lld", &u, &v, &w);
		AddEdge(u, v, w);
	}
	printf("%lld", Edmonds_Karp());
	return 0;
}
2021/4/9 15:05
加载中...