蒟蒻的Dinic怎么这么慢?
查看原帖
蒟蒻的Dinic怎么这么慢?
1064609
gty271828楼主2023/10/28 10:59

对着置顶题解写的,可是那篇题解 100ms 不到,我的都跑 1s 左右。

都快改得一模一样了,可是越改越慢

#include <bits/stdc++.h>

#define F(i, a, b) for(int i = a; i <= (b); ++i)
#define dF(i, a, b) for(int i = a; i >= (b); --i)

using namespace std;
typedef long long LL;
typedef unsigned long long ull;
const int N = 205;
const int M = 5e3 + 5;
const LL inf = 1e18;

int n, m, s, t;
LL ans;

int tot = 1, head[N];
struct edge { int nxt, v; LL w; } e[M << 1];
void Addedge(int u, int v, int w) {
	e[++tot] = {head[u], v, w};
	head[u] = tot;
	return ;
}

int now[N];
LL dis[N];
bool Bfs() {
	F(i, 1, n) dis[i] = inf;
	queue<int> q;
	q.push(s);
	dis[s] = 0;
	now[s] = head[s];
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].v, w = e[i].w;
			if (w > 0 && dis[v] == inf) {
				dis[v] = dis[u] + 1;
				now[v] = head[v];
				if (v == t) return 1;
				q.push(v);
			}
		}
	}
	return 0;
}
LL Dfs(int u, LL sum) {
	if (u == t) return sum;
	LL res = 0, r;
	for (int i = now[u]; i; i = e[i].nxt) {
		now[u] = i;
		int v = e[i].v;
		if (e[i].w > 0 && dis[v] == dis[u] + 1) {
			r = Dfs(v, min(sum, e[i].w));
			if (!r) dis[v] = inf;
			e[i].w -= r;
			e[i ^ 1].w += r;
			res += r;
			sum -= r;
		}
	}
	return res;
}

int main() {
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> s >> t;
	F(i, 1, m) {
		int u, v, w;
		cin >> u >> v >> w;
		Addedge(u, v, w);
		Addedge(v, u, 0);
	}
	while (Bfs()) ans += Dfs(s, inf);
	cout << ans;
	return 0;
}
2023/10/28 10:59
加载中...