HLPP求调
查看原帖
HLPP求调
551861
strcmp楼主2022/3/4 21:02

经过判断是因为结点还未推送到汇点 t 就将余流退回了源点 s,请问代码逻辑有什么问题吗?

Hack

input:
10 30 3 7
10 2 18652
8 9 2560
8 9 13734
5 6 23138
9 7 29606
5 8 21673
1 9 11596
3 2 9441
3 7 4829
5 8 24437
1 2 31111
4 10 26213
2 7 31808
1 9 10841
6 8 10758
3 5 11887
4 2 1362
4 1 18182
4 8 18156
10 6 11015
2 7 2640
10 6 27726
10 6 21615
5 1 5959
3 1 19857
5 4 1862
8 9 13830
3 10 22152
4 10 5221
5 2 24065
output:
68166

wrong output:
26157

code:

#include <bits/stdc++.h>
using namespace std;
#define inf 1000000000000000
#define V 50010
#define E 1000010
typedef long long int ll;
struct edge {
public:
	int to, next;
	ll capa;
};
int cnt = 0, head[V]; int n, m; vector<edge>node(E);
inline void add(int fir, int nxt, ll w) {		
	node[cnt].to = nxt;
	node[cnt].capa = w;
	node[cnt].next = head[fir];
	head[fir] = cnt; ++cnt;
}
int s, t, dep[V], gap[V]; queue<int>que; ll sum = 0; ll cur[V];
bool inque[V];
inline void initing() { memset(dep, -1, V * sizeof(int)); }
inline void bfs() {
	int fro, ito;
	que.push(t); dep[t] = 0; ++gap[dep[t]];
	while (!que.empty()) {
		fro = que.front(); que.pop();
		for (register int i = head[fro]; i != -1; i = node[i].next) {
			ito = node[i].to;
			if (dep[ito] == -1) {
				dep[ito] = dep[fro] + 1;
				que.push(ito);
				++gap[dep[ito]];
			}
		}
	}
}
struct cmp {
public:
	inline bool operator()(int a, int b) {return dep[a] < dep[b];}
};
priority_queue<int, vector<int>, cmp>hlpp;
void push(int v) {
	for (int i = head[v]; i != -1; i = node[i].next) {
		if (!cur[v])return;
		if (dep[v] == dep[node[i].to] + 1 && node[i].capa) {
			ll ls = min(cur[v], node[i].capa);
			cur[v] -= ls, cur[node[i].to] += ls;
			node[i].capa -= ls, node[i ^ 1].capa += ls;
			if (!inque[node[i].to] && node[i].to != s && node[i].to != t) {
				hlpp.push(node[i].to);
				inque[node[i].to] = true;
			}
		}
	}
}
void relable(int v) {
	dep[v] = n + 1;
	for (register int i = head[v]; i != -1; i = node[i].next) {
		if (node[i].capa && dep[v] > dep[node[i].to] + 1)
			dep[v] = dep[node[i].to] + 1;
	}
}
ll HLPP() {
	cur[s] = inf; initing(); bfs();
	int np; int v; ll w; ll ans = 0;
	for (int i = head[s]; i != -1; i = node[i].next) {
		v = node[i].to; w = node[i].capa;
		cur[s] -= w; cur[v] += w;
		node[i].capa -= w; 
		node[i ^ 1].capa += w;
		if (v != s && v != t) { hlpp.push(v); inque[v] = true; }
	}
	while (!hlpp.empty()) {
		np = hlpp.top(); hlpp.pop();
		relable(np);
		inque[np] = false;
		push(np);
		if (cur[np]) {
			if (--gap[dep[np]] == 0) {
				for (int i = 1; i <= n; i++)
					if (i != s && i != t && dep[i] > dep[np] && dep[i] < n + 1)
						dep[i] = n + 1;
			}
			relable(np);
			++gap[dep[np]];
			hlpp.push(np);
			inque[np] = true;
		}
	}
	return cur[t];
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(); cout.tie();
	memset(head, -1, V * sizeof(int));
	cin >> n >> m >> s >> t;
	int f, l; ll w;
	for (register int i = 0; i < m; i++) {
		cin >> f >> l >> w;
		add(f, l, w);
		add(l, f, 0);
	}
	cout << HLPP();
	return 0;
}
2022/3/4 21:02
加载中...