为什么代码就执行了两次?
  • 板块灌水区
  • 楼主呆呆的她啊
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/12/17 23:27
  • 上次更新2023/12/18 00:47:08
查看原帖
为什么代码就执行了两次?
226167
呆呆的她啊楼主2023/12/17 23:27

rt bfs进去第二次h[4]就等于0了,

我就很纳闷,我都没修改他呀 然后后面就没法正常走了 给出样例

4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 30
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int M = 10005;
const int N = 5005;
int n, m, s, t;
struct node {
	ll v, c, next;
} e[M];
int h[M], cur[N], d[N];;
int a, b, c, idx=0;
inline int read() {
	int s = 0;
	char ch = getchar();
	while (ch >= '0' && ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s;
}
bool bfs() {
	//cout<<"sss";
	queue<int>q;
	memset(d, 0, sizeof d);
	q.push(s);
	d[s] = 1;
	while (q.size()) {
		int u = q.front();
		q.pop();
		cout<<u<<" ";
		cout<<h[u]<<endl;
		for (int i = h[u]; i; i = e[i].next) {
			int v = e[i].v;
			if (d[v] == 0 && e[i].c) {
				d[v] = d[u] + 1;
				q.push(v);
				if (v == t)return true;
			}
		}
	}
	return false ;
}
ll  dfs( int u, ll mf) {
	if (u == t)return mf;
	ll sum = 0;
	for (int i = cur[u]; i; i = e[i].next) {
		int v = e[i].v;
		if (d[v] == d[u] + 1 && e[i].c) {
			cur[u] = i;
			ll f = dfs(v, min(e[i].c, mf));
			sum += f;
			e[i].c -= f;
			e[i ^ 1].c += f;
			mf -= f;
			if (mf == 0)break;
		}
	}
	if (sum == 0)d[u] = 0;
	return sum;
}
ll dinic() {
	ll flow = 0;
	while (bfs()) {
		memcpy(cur, h, sizeof h);
		flow += dfs(s, 1e9);
	}
	return flow;
}
int main() {
	n = read(), m = read();
	s = read(), t = read();
	memset(h,0,sizeof h);
	for (int i = 1; i <= m; i++) {
		a = read(), b = read(), c = read();
		e[++idx] = {b, c, h[a]};
		h[a] = idx;
		e[++idx]={a,0,h[b]};
		h[b]=idx;
	}
	cout << dinic();
	return 0;
}


2023/12/17 23:27
加载中...