费用流板子 90pts 求助
查看原帖
费用流板子 90pts 求助
226449
Horizon_Blue楼主2024/2/27 06:55
#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;
}
2024/2/27 06:55
加载中...