求助
查看原帖
求助
608410
封禁用户楼主2024/11/6 19:35

EK刚学1ms,死循环了。

#include<bits/stdc++.h>

namespace IO {
	inline int read() {
		int ret = 0, f = 1;char ch = getchar();
		while (ch < '0' || ch > '9') {
			if (ch == '-') f = -f;
			ch = getchar();
		}
		while (ch >= '0' && ch <= '9') {
			ret = (ret << 1) + (ret << 3) + (ch ^ 48);
			ch = getchar();
		}
		return ret * f;
	}
	void write(int x) {
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) write(x / 10);
		putchar(x % 10 + '0');
	}
} 

using namespace std;
using namespace IO;

const int maxn = 200 + 5;
const int maxm = 5e3 + 5;

int tot = 1, head[maxn], to[maxm * 2], nxt[maxm * 2], val[maxm * 2];
void add(int u, int v, int c) {
	tot++;
	nxt[tot] = head[u];
	head[u] = tot;
	to[tot] = v;
	val[tot] = c;
}

int n, m, s, t;

struct Node {
	int num, edge;
};

queue<int> q;
int vis[maxm * 2];
Node pre[maxm * 2];
bool bfs() {
	memset(vis, 0, sizeof(vis));
	memset(pre, -1, sizeof(pre));
	q.push(s);
	vis[s] = 1;
	while (!q.empty()) {
		int now = q.front();q.pop();
		for (int i = head[now];i;i = nxt[i]) {
			int v = to[i], Val = val[i];
			if (Val && !vis[v]) {
				pre[v].num = now;
				pre[v].edge = i;
				if (v == t) return 1;
				vis[v] = 1;
				q.push(v);
			}
		}
	}
	return 0;
}

int ans;

void EK() {
	while (bfs()) {
		int minn = INT_MAX;
		for (int i = t;i != s;i = pre[i].num) minn = min(minn, val[pre[i].edge]);
		ans += minn;
		for (int i = t;i != s;i = pre[i].num) {
			val[pre[i].edge] -= minn;
			val[pre[i].edge ^ 1] += minn;
		}
	}
}

int main() {
	n = read(), m = read(), s = read(), t = read();
	for (int i = 1;i <= m;i++) {
		int u = read(), v = read(), c = read();
		add(u, v, c), add(v, u, 0);
	}
	
	EK();
	
	printf("%d\n", ans);
	return 0;
}
2024/11/6 19:35
加载中...