编辑
2025-08-30
XCPC
00
请注意,本文编写于 141 天前,最后修改于 136 天前,其中某些信息可能已经过时。
#include <bits/stdc++.h> using namespace std; #define int long long const int M = 1e5 + 5; int a[M], cnt = 1, vis[M]; int n, m, s, t; int head[M], pre[M], mf[M], dis[M]; struct dian { int to, c, w, ne; } f[M]; int cost, flow; void add(int x, int y, int c, int w) { f[++cnt].to = y; f[cnt].c = c; f[cnt].w = w; f[cnt].ne = head[x]; head[x] = cnt; f[++cnt].to = x; f[cnt].c = 0; f[cnt].w = -w; f[cnt].ne = head[y]; head[y] = cnt; } int bfs() { for (int i = 1; i <= n; ++i) mf[i] = 0; mf[s] = 1e18; for (int i = 1; i <= n; ++i) dis[i] = 1e18; dis[s] = 0; queue<int> p; p.push(s); vis[s] = 1; while (!p.empty()) { int t = p.front(); p.pop(); vis[t] = 0; for (int i = head[t]; i; i = f[i].ne) { int to = f[i].to, c = f[i].c, w = f[i].w; if (c && dis[t] + w < dis[to]) { dis[to] = dis[t] + w; mf[to] = min(mf[t], c); pre[to] = i; if (!vis[to]) vis[to] = 1, p.push(to); } } } return mf[t] > 0; } void ek() { while (bfs()) { int now = t; while (now != s) { int q = pre[now]; f[q].c -= mf[t]; f[q ^ 1].c += mf[t]; now = f[q ^ 1].to; } flow += mf[t]; cost += mf[t] * dis[t]; } } void solve() { cin >> n >> m >> s >> t; cnt = 1; while (m--) { int a, b, c, d; cin >> a >> b >> c >> d; add(a, b, c, d); } ek(); cout << flow << ' ' << cost; for (int i = 1; i <= n; ++i) { vis[i] = head[i] = mf[i] = pre[i] = dis[i] = 0; } } signed main() { ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); int T = 1; // cin>>T; while (T--) solve(); return 0; }
如果对你有用的话,可以打赏哦
打赏
ali pay
wechat pay