(悬关)不输出结果QWQ
查看原帖
(悬关)不输出结果QWQ
704668
WZWZWZWY楼主2024/2/23 21:55

无可奈何WA落去,似曾相识T归来。

准确的说不是T了,是不输出结果。

抄的是 https://www.luogu.com.cn/paste/hakjys6r

这个代码。 到底哪里抄错了啊……悬关 /bx

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int inf = 1ll << 30;

int top = 1, head[10100], n, m, s, t;
int e[10100], h[10100], cnth[20100]; // 每个点对应的余流,高度;每个高度有多少个点 

struct cmp {
	inline bool operator () (int a, int b) const {
		return h[a] < h[b];
	}
};

struct Node {
	int v, val, Next;
} node[400100];

inline void add(int u, int v, int val) {
	node[++top].v = v; node[top].val = val; node[top].Next = head[u]; head[u] = top;
	node[++top].v = u; node[top].val = 0;   node[top].Next = head[v]; head[v] = top;
}

int inque[11000];

void bfs() {
	memset(h, 0x3f, sizeof(h));
	h[t] = 0;
	queue <int> q; q.push(t);
	while (q.size()) {
		int u = q.front(); q.pop();
		inque[u] = 0;
		for (int i = head[u]; i; i = node[i].Next) {
			int d = node[i].v;
			if (node[i ^ 1].val && h[d] > h[u] + 1) { // 反向跑 
				h[d] = h[u] + 1;
				if (inque[d] == 0) {
					q.push(d);
					inque[d] = 1;
				}
			}
		}
	}
}

priority_queue <int, vector<int>, cmp> q;
inline void push_(int u) { // 推流 
	for (int i = head[i]; i; i = node[i].Next) {
		int d = node[i].v;
		if (node[i].val && h[d] + 1 == h[u]) { // 可以推流 
			int minn = min(node[i].val, e[u]);
			node[i].val -= minn;
			node[i ^ 1].val += minn;
			e[u] -= minn; e[d] += minn;
			if (inque[d] == 0 && d != s && d != t) {
				q.push(d);
				inque[d] = 1;
			}
			if (e[u] == 0) break; // 已经推完了 
		}
	}
}

inline void relabel(int u) { // 翻译:重新贴标签。把 u 的高度更改为与 u 相邻的最低点的高度 + 1 
	h[u] = inf;
	for (int i = head[u]; i; i = node[i].Next) {
		int d = node[i].v;
		if (node[i].val && h[d] + 1 < h[u]) h[u] = h[d] + 1;
	}
}

int HLPP() {
	bfs();
	if (h[s] == 0x3f3f3f3f) return 0; // s 与 t 不连通 
	h[s] = n;
	for (int i = 1; i <= n; i++) 
		if (h[i] < 0x3f3f3f3f) cnth[h[i]] ++; // 统计 各个高度的点数,下标不要越界
	for (int i = head[s]; i; i = node[i].Next) { // 从 s 向周围点推流 
		int d = node[i].v, minn = node[i].val;
		if (minn) {
			e[s] -= minn; e[d] += minn;
			node[i].val -= minn; node[i ^ 1].val += minn;
			if (d != t && inque[d] == 0 && d != s) {
				q.push(d);
				inque[d] = 1;
			}
		}
	}
	
	while(q.size()) {
		int u = q.top(); q.pop();
		inque[u] = 0;
		push_(u);
		if (e[u]) { // 还有余流 
			if (--cnth[h[u]] == 0) // gap优化 
				for (int i = 1; i <= n; i++)
					if (i != s && i != t && h[i] > h[u] && h[i] <= n) 
						h[i] = n + 1; //标记无法到达
			relabel(u);
			cnth[h[u]] ++;
			q.push(u); inque[u] = 1;
		}
	}
	return e[t];
}

signed main() {
	//cin.tie(0); ios::sync_with_stdio(0);
	cin >> n >> m >> s >> t;
	for (int i = 1; i <= m; i++) {
		int u, v, val;
		cin >> u >> v >> val;
		add(u, v, val);
	}
	cout << HLPP();
}
2024/2/23 21:55
加载中...