萌新 Dinic 求调
查看原帖
萌新 Dinic 求调
610557
shinzanmonoszm 妹妹楼主2023/1/18 19:16
#include<iostream>
#include<algorithm>
#include<limits>
#include<queue>
const int sz = 5e3 + 10;
const int msz = 5e4 + 10;
using ll = long long;
const ll inf = std::numeric_limits<ll>::max() / 2;
struct edge {
    int nxt, to, cap, w;
} graph[msz << 1];
int hpp = 1, head[sz], chead[sz];
void addEdge(int from, int to, int cap, int cost) {
    graph[++hpp] = edge{head[from], to, cap, cost};
    head[from] = hpp;
}
bool inq[sz];
ll dis[sz];
int n, m, s, t;
std::queue<int> qq;
bool spfa() {
    std::fill(dis + 1, dis + n + 1, inf);
    std::fill(inq + 1, inq + n + 1, 0);
    std::copy(head + 1, head + n + 1, chead + 1);
    dis[s] = 0, qq.push(s);
    inq[s] = 1;
    while (!qq.empty()) {
        int u = qq.front();
        qq.pop(), inq[u] = 0;
        for (int p = head[u]; p; p = graph[p].nxt) {
            int v = graph[p].nxt;
            if (dis[v] > dis[u] + graph[p].w && graph[p].cap) {
                dis[v] = dis[u] + graph[p].w;
                if (!inq[v]) qq.push(v), inq[v] = 1;
            }
        }
    }
    return dis[t] != inf;
}
ll cost;
ll dfs(int u, ll lim) {
    if (u == t || lim == 0) return lim;
    ll path = 0, arc = 0;
    for (int p = chead[u]; p && lim; p = graph[p].nxt) {
        chead[u] = p;
        int v = graph[p].to;
        ll w = graph[p].cap;
        if (dis[v] = dis[u] + graph[p].w && w != 0) {
            arc = dfs(v, std::min(w, lim));
            path += arc, lim -= arc;
            graph[p].cap -= arc, graph[p ^ 1].cap += arc; 
            cost += graph[p].w * arc;
        }
    }
    return path;
}
ll dinic() {
    ll res = 0;
    while (spfa())
        res += dfs(s, inf);
    return res;
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n >> m >> s >> t;
    for (int i = 1, u, v, w, c; i <= m; i++) 
        std::cin >> u >> v >> w >> c, addEdge(u, v, w, c), addEdge(v, u, 0, -c);
    std::cout << dinic() << " " << cost;
    return 0;
}
2023/1/18 19:16
加载中...