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;
}
如果找不到,有没有一份邻接表的最大流?