#include <bits/stdc++.h>
#ifdef ONLINE_JUDGE
#define freopen(...) 0
#endif
#define V vector
#define fi first
#define se second
#define ins emplace
#define eb emplace_back
#define FO(i, a, b) F(i, a, (b) - 1)
#define RO(i, a, b) R(i, a, (b) - 1)
#define F(i, a, b) for (int i = (a), iee = (b); i <= iee; i++)
#define R(i, a, b) for (int i = (b), iee = (a); i >= iee; i--)
#define rsz resize
#define sz(x) (x).size()
#define BE(x) begin(x), end(x)
#define BN(x, n) ((x) + 1), ((x) + (n) + 1)
using namespace std;
using str = string;
using ll = long long;
using u32 = unsigned;
using db = long double;
using i128 = __int128_t;
using u128 = __uint128_t;
using u64 = decltype(1ull);
template <typename T, typename U = less<>>
using pq = priority_queue<T, V<T>, U>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return rng() % (r - l + 1) + l; }
auto chkmn = [](auto &x, const auto &y) { return x > y ? (x = y, 1) : 0; };
auto chkmx = [](auto &x, const auto &y) { return x < y ? (x = y, 1) : 0; };
template <typename T, int N, int M>
struct mcmf {
static const T inf = (T)0x3f3f3f3f3f3f3f3f;
struct edge {
int v, nxt;
T w, c; // capacity, cost
} e[M << 1];
int n, s, t, head[N], cur[N], cnt;
T dis[N], phi[N];
int vis[N];
mcmf(): head(), cnt(1) {}
void reset(int n_, int s_, int t_) {
n = n_, s = s_, t = t_, fill(BN(head, n), 0), cnt = 1;
}
void arc(int u, int v, T w, T c) {
e[++cnt] = edge{v, head[u], w, c}, head[u] = cnt;
}
void add(int u, int v, T w, T c) {
arc(u, v, w, c), arc(v, u, 0, -c);
}
T flow, cost;
T dfs(int x, T f) {
if (x == t) return flow += f, cost += phi[s] * f, f;
T t = f;
vis[x] = 1;
for (int &i = cur[x]; i; i = e[i].nxt) {
if (e[i].w && phi[e[i].v] - phi[x] + e[i].c == 0 && !vis[e[i].v]) {
T p = dfs(e[i].v, min(f, e[i].w));
e[i].w -= p, e[i ^ 1].w += p, f -= p;
if (!f) break;
}
}
return t - f;
}
bool relabel() {
T gap = inf;
F(i, 1, n) if (vis[i])
for (int j = head[i]; j; j = e[j].nxt)
if (e[j].w && !vis[e[j].v])
gap = min(gap, phi[e[j].v] - phi[i] + e[j].c);
if (gap == inf) return 0;
F(i, 1, n) if (vis[i]) phi[i] += gap;
return 1;
}
void zkw() {
flow = 0, cost = 0;
fill(BN(phi, n), 0);
do do fill(BN(vis, n), 0), copy(BN(head, n), cur + 1);
while (dfs(s, inf));
while (relabel());
}
void spfa() {
fill(BN(vis, n), 0);
fill(BN(dis, n), inf);
queue<int> q;
dis[t] = 0, q.push(t);
while (!q.empty()) {
int x = q.front(); q.pop(); vis[x] = 0;
for (int i = head[x]; i; i = e[i].nxt)
if (e[i ^ 1].w && chkmn(dis[e[i].v], dis[x] - e[i].c) && !vis[e[i].v]++)
q.push(e[i].v);
}
copy(BN(dis, n), phi + 1);
}
bool dij() {
fill(BN(vis, n), 0);
fill(BN(dis, n), inf);
pq<pair<T, int>> q;
dis[t] = 0, q.emplace(phi[t] - dis[t], t);
while (!q.empty()) {
int x = q.top().se; q.pop();
if (vis[x]) continue;
vis[x] = 1;
for (int i = head[x]; i; i = e[i].nxt) {
int v = e[i].v;
if (e[i ^ 1].w && chkmn(dis[v], dis[x] - e[i].c))
q.emplace(phi[v] - dis[v], v);
}
}
copy(BN(dis, n), phi + 1);
return vis[s];
}
void pd() {
flow = 0, cost = 0;
spfa();
do do fill(BN(vis, n), 0), copy(BN(head, n), cur + 1);
while (dfs(s, inf));
while (dij());
}
};
mcmf<int, 5100, 50100> G;
int main() {
freopen("AGC043F.in", "r", stdin),
freopen("AGC043F.out", "w", stdout),
cin.tie(0)->sync_with_stdio(0);
int n, m, s, t;
cin >> n >> m >> s >> t;
G.reset(n, s, t);
F(i, 1, m) {
int u, v, w, c;
cin >> u >> v >> w >> c;
G.add(u, v, w, c);
}
G.pd();
cout << G.flow << " " << G.cost << "\n";
}
错误信息:
/nix/store/js66s0xwjnzg0ggi2lq9bcvlk6x2za13-binutils-2.35.2/bin/ld: ./cccp4N2U.o: in function `mcmf<int, 5100, 50100>::spfa()':
src:(.text._ZN4mcmfIiLi5100ELi50100EE4spfaEv[_ZN4mcmfIiLi5100ELi50100EE4spfaEv]+0x86): undefined reference to `mcmf<int, 5100, 50100>::inf'
/nix/store/js66s0xwjnzg0ggi2lq9bcvlk6x2za13-binutils-2.35.2/bin/ld: ./cccp4N2U.o: in function `mcmf<int, 5100, 50100>::dij()':
src:(.text._ZN4mcmfIiLi5100ELi50100EE3dijEv[_ZN4mcmfIiLi5100ELi50100EE3dijEv]+0x86): undefined reference to `mcmf<int, 5100, 50100>::inf'
collect2: 错误:ld 返回 1
但是这个 inf 在更靠前的位置出现过(函数 relabel,zkw),却没有报错,这是为什么?