dij 费用流

#include <bits/stdc++.h>

using namespace std;

typedef long long lld;

const int MAXN = 50010, MAXM = 1000010, INF = 0x3f3f3f3f;

struct Edge { int to, next, cap, flow, cost; } edge[MAXM];

int head[MAXN], tol, pre[MAXN], dis[MAXN], h[MAXN];

struct Node { int x, dis; bool operator<(Node b) const { return b.dis < dis; } };

priority_queue<Node> Q;

void init() {

	tol = 0; memset(head, -1, sizeof(head));

}

void addedge(int u, int v, int cap, int cost) {

	edge[tol] = (Edge){ v, head[u], cap, 0, cost }; head[u] = tol++;

	edge[tol] = (Edge){ u, head[v], 0, 0, -cost }; head[v] = tol++;

}

bool dijkstra(int s, int t, int N) {

    for (int i = 0; i <= N; i++)

        h[i] = min(h[i] + dis[i], INF), dis[i] = INF, pre[i] = -1;

    dis[s] = 0, Q.push(Node { s, 0 });

    while (!Q.empty()) {

        int u = Q.top().x, dist = Q.top().dis; Q.pop();

        if (dist > dis[u]) continue;

        for (int i = head[u]; ~i; i = edge[i].next) {

            Edge& e = edge[i]; int v = edge[i].to;

            if (e.cap > e.flow && dis[v] > dis[u] + e.cost + h[u] - h[v]) {

                dis[v] = dis[u] + e.cost + h[u] - h[v], pre[v] = i;

                Q.push(Node { v, dis[v] });

            }

        }

    }

    return dis[t] < INF;

}

pair<int,int> minCostMaxFlow(int s, int t, int N) {

	int flow = 0, cost = 0;

	while (dijkstra(s, t, N)) {

		int Min = INF, Fee = dis[t] + h[t] - h[s];

		for (int i = pre[t]; ~i; i = pre[edge[i^1].to])

			Min = min(Min, edge[i].cap - edge[i].flow);

		for (int i = pre[t]; ~i; i = pre[edge[i^1].to])

			edge[i].flow += Min, edge[i^1].flow -= Min;

		flow += Min, cost += Fee * Min;

	}

	return make_pair(flow, cost);

}

int main()

{

    init(); int n, m, s, t, u, v, w, f;

    scanf("%d %d %d %d", &n, &m, &s, &t);

    for (int i = 1; i <= m; i++)

        scanf("%d %d %d %d", &u, &v, &w, &f),

        addedge(u, v, w, f);

    auto ans = minCostMaxFlow(s, t, n);

    printf("%d %d\n", ans.first, ans.second);

    return 0;

}
巴特西

dij 费用流

最新文章

热门文章
