网络流
  • 板块学术版
  • 楼主shadow_ltq
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/9/19 19:35
  • 上次更新2023/10/27 10:36:11
查看原帖
网络流
384233
shadow_ltq楼主2022/9/19 19:35

死循环了

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define db double

const int N = 1e2 + 10, M = 1e4 + 10;
int n, m, s, t, dis[N], pre[N];
int idx, h[N], w[M], to[M], ne[M];
ll ans;
bool has[N];

void add (int x, int y, int c)
{
	to[++idx] = y;
	ne[idx] = h[x];
	w[idx] = c;
	h[x] = idx;
	to[++idx] = x;
	ne[idx] = h[y];
	w[idx] = 0;
	h[y] = idx;
}

bool bfs ()
{
	memset (has, false, sizeof (has));
	queue <int> q;
	q.push (s);
	has[s] = true;
	dis[s] = INT_MAX;
	while (q.size ())
	{
		int x = q.front ();
		q.pop ();
		for (int i = h[x]; i; i = ne[i])
		{
			if (w[i])
			{
				int y = to[i];
				if (has[y])
				{
					continue;
				}
				dis[y] = min (dis[x], w[i]);
				pre[y] = i;
				q.push (y);
				has[y] = true;
				if (y == t)
				{
					return true;
				}
			}
		}
	}
	return false;
}

void update ()
{
	int x = t;
	while (x != s)
	{
		int i = pre[x];
		w[i] -= dis[t];
		w[i ^ 1] += dis[t];
		x = to[i ^ 1];
	}
	ans += dis[t];
}

int main()
{
	scanf ("%d%d%d%d", &n, &m, &s, &t);
	for (int i = 1; i <= m; i++)
	{
		int a, b, c;
		scanf ("%d%d%d", &a, &b, &c);
		add (a, b, c);
	}
	while (bfs ())
	{
		update ();
	}
	printf ("%lld", ans);
	return 0;
}
2022/9/19 19:35
加载中...