网络流求助P3376
  • 板块学术版
  • 楼主lwx20211103
  • 当前回复11
  • 已保存回复11
  • 发布时间2023/8/13 17:25
  • 上次更新2023/11/3 04:03:58
查看原帖
网络流求助P3376
727008
lwx20211103楼主2023/8/13 17:25

rt,我的代码一直死循环,不知道是卡在哪里了

// Problem: P3376 【模板】网络最大流
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3376
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define p_b push_back
#define ft first
#define nd second
#define pii pair<int, int>
#define pll pair<long long, long long>

using namespace std;

typedef long long ll;

ll n, m, s, t, d[5005], cur[5005];
bool mark[5005];

struct graph
{
	ll from, to, cap, val;//起点,终点,容量,流量
};

vector<graph> edge;
vector<ll> g[505];

bool bfs()
{
	queue<ll> q;
	// memset(d, 0, sizeof(d));
	memset(mark, 0, sizeof(mark));
	q.push(s), d[s] = 0	, mark[s] = 1;
	while (!q.empty())
	{
		ll hd = q.front();
		q.pop();
		for (auto i : g[hd])
		{
			graph x = edge[i];
			if (!mark[x.to] && x.cap > x.val)
			{
				mark[x.to] = 1;
				d[x.to] = d[hd] + 1;
				q.push(x.to);
			}
		}
	}
	return mark[t];
}

ll dfs(ll x, ll a)
{
	if (x == t && !a)
		return a;
	ll flow = 0, f;
	for (int i = cur[x]; i < g[x].size(); i++)
	{
		cur[x] = i;
		graph e = edge[g[x][i]];
		if (d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap - e.val))) > 0)
		{
			e.val += f;
			edge[g[x][i] ^ 1].val -= f;
			flow += f;
			a -= f; 
			if (!a) break;
		}
	}
	return flow;
}

ll maxflow()
{
	ll flow = 0;
	while (bfs())
	{
		memset(cur, 0, sizeof(cur));
		flow += dfs(s, 1145141919810);
	}
	return flow;
}

int main()
{
	cin >> n >> m >> s >> t;
	for (int i = 1; i <= m; i++)
	{
		ll u, v, c;
		cin >> u >> v >> c;
		edge.p_b({u, v, c, 0});
		edge.p_b({v, u, 0, 0});
		int s = edge.size();
		g[u].p_b(s - 2);
		g[v].p_b(s - 1);
	}
	cout << maxflow();
	return 0;
}

如果找不到,有没有一份邻接表的最大流?

2023/8/13 17:25
加载中...