你这数据太假了
查看原帖
你这数据太假了
895690
gghack_Nythix楼主2025/1/21 08:28

rt,一个当前弧优化写错了的代码怎么过的?

# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N = 800 , INF = 1e18;
int n , m , cur = 1 , s , t , pre[N << 5] , nxt[N << 5] , head[N << 5] , edge[N << 5] , to[N << 5] , ceng[N << 5] , maxflow , tmp[N << 5];
void addedge (int u , int v , int w) {nxt[++cur] = head[u] , edge[cur] = w , to[cur] = v , head[u] = cur;}
bool bfs () {
	memset (ceng , 0 , sizeof ceng);
	queue <int> q;
	q.push (s) , ceng[s] = 1;
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		tmp[now] = head[now];//部分节点可能在此不会被更新tmp[now],导致我最大流的图用了一部分上次的残留下来的图
		for (int i = head[now];i ;i = nxt[i]) {
			int y = to[i];
			if (edge[i] && !ceng[y]) {
				ceng[y] = ceng[now] + 1 , q.push (y);
				if (y == t) return 1;	
			}
		}
	}
	return 0;
}
int dinic (int now , int flow) {
	if (now == t) return flow;
	int rest = flow;
	for (int i = tmp[now] ; i && rest; i = nxt[i]) {
		int y = to[i];
		tmp[now] = i;
		if (ceng[y] == ceng[now] + 1 && edge[i]) {
			int inc = dinic (y , min(rest , edge[i]));
			if (inc == 0) ceng[y] = 0;
			edge[i] -= inc , edge[i ^ 1] += inc , rest -= inc;
		}
	}
	return flow - rest;
}
signed main () {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	memset (head , 0 , sizeof head);
	cin >> n >> m >> s >> t;
	for (int i = 1;i <= m;++i) {
		int u , v , w;
		cin >> u >> v >> w;
		addedge (u , v , w);
		addedge (v , u , 0);
	}
	while (bfs()) maxflow += dinic (s , INF);
	cout << maxflow << '\n';
	return 0;
}

至于hack,把 P2598 的后四个点建模之后的图拿过来就行了。

2025/1/21 08:28
加载中...