费用流板子 90pts 求助

P3381 【模板】最小费用最大流

这码风蚌埠住了。你是来搞笑的吗。
by scp020 @ 2024-02-27 08:10:32


幽默,发出来让别人调之前先把压行去掉吧。
by Drind @ 2024-02-27 08:17:25


我觉得这个码风挺正常的吧
by TernaryTree @ 2024-02-27 08:17:58


@[scp020](/user/553625) 百度一个代码格式化器也就花两秒钟时间。。 ``` #include <iostream> #include <queue> #define int long long using namespace std; vector<int> g[5005], cap[5005], rev[5005], ww[5005]; int dis[5005], vis[5005]; bool vis2[5005]; queue<int> q; signed main() { int n, m, s, t, u, v, w, c, x, summ=0, cst=0, ans=0, minn=0; cin >> n >> m >> s >> t; for (int i=1; i<=m; i++) cin >> u >> v >> w >> c, g[u].push_back(v), g[v].push_back(u), cap[u].push_back(w), cap[v].push_back(0), rev[u].push_back(g[v].size()-1), rev[v].push_back(g[u].size()-1), ww[u].push_back(c), ww[v].push_back(-c); do { summ += minn; for (int i=1; i<=n; i++) vis[i] = vis2[i] = 0, dis[i] = 0x3fffffff; dis[s] = 0; q.push(s); vis[s] = 114514; while (!q.empty()) { x = q.front(); q.pop(); vis2[x] = 0; for (int i=0; i<g[x].size(); i++) if (dis[g[x][i]] > dis[x] + ww[x][i] && cap[x][i]) { vis[g[x][i]] = rev[x][i]+1, dis[g[x][i]] = dis[x] + ww[x][i], !vis2[g[x][i]] && (q.push(g[x][i]), vis2[v] = 1); } } if (!vis[t]) break; for (int i=1; i<=n; i++) if (vis[i]) vis[i]--; minn = 0x3fffffff; for (int i=t; i!=s; i=g[i][vis[i]]) minn = min(minn, cap[g[i][vis[i]]][rev[i][vis[i]]]); for (int i=t; i!=s; i=g[i][vis[i]]) cap[g[i][vis[i]]][rev[i][vis[i]]] -= minn, cap[i][vis[i]] += minn, cst += minn * ww[g[i][vis[i]]][rev[i][vis[i]]]; } while (minn); cout << summ << ' ' << cst; } ```
by lonely_seele @ 2024-02-27 09:09:41


@[lonely_seele](/user/226449) 我用vscode可以一键格式化,不需要百度
by scp020 @ 2024-02-27 12:30:12


@[scp020](/user/553625) 那我不知道你在求条帖下面评论别人的习惯是想表达什么/qd
by lonely_seele @ 2024-02-27 13:00:27


@[lonely_seele](/user/226449) 呃
by scp020 @ 2024-02-27 13:43:10


对不起 我唐了 `g[x][i]` 给我写成 `v` 了 这破玩意也能拿到 90pts 可见这题的数据有多水。。
by lonely_seele @ 2024-02-28 13:19:45


|