求助 CE
  • 板块学术版
  • 楼主Misaka14285
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/5/27 09:34
  • 上次更新2023/10/23 14:39:43
查看原帖
求助 CE
550235
Misaka14285楼主2023/5/27 09:34
#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),却没有报错,这是为什么?

2023/5/27 09:34
加载中...