Luogu ~ P2604 [ZJOI2010] ~ Network expansion (minimum cost maximum flow)

First question: Jianbian u->v capacity is the capacity in the title, the cost is 0, the maximum flow obtained by running the fee flow is the answer.

第二问: Jianbian u->v capacity is INF, cost in the cost of the question, the cost of running the cost stream is the answer.

#include<bits/stdc++.h>
Using namespace std;
Const int MAXN = 1e5 + 5;
Const int INF = 0x3f3f3f3f;
Struct edge
{
    Int from, to, cap, flow, cost; //start, end point, capacity, flow, cost
    Edge(int u, int v, int c, int f, int w): from(u), to(v), cap(c), flow(f), cost(w) {}
};
Struct MCMF
{
    Int n, m; //number of nodes, number of edges (including reverse arc), source point s, sink point t
    Vector<Edge> edges; //side table. Edges[e] and edges[e^1] are reverse arcs
    Vector<int> G[MAXN]; // adjacency list, G[i][j] represents the sequence number of the jth edge of node i in the edges array
    Bool inq[MAXN]; //whether in the queue
    Int d[MAXN]; //Bellman-Ford
    Int p[MAXN]; //previous arc
    Int a[MAXN]; // can improve

    Void init(int n)
    {
        This->n = n;
        Edges.clear();
        For (int i = 0; i <= n; i++) G[i].clear();
    }

    Void AddEdge(int from, int to, int cap, int cost)
    {
        Edges.push_back(Edge(from, to, cap, 0, cost));
        Edges.push_back(Edge(to, from, 0, 0, -cost));
        m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }

    Bool BellmanFord(int s, int t, int &flow, long long& cost)//SPFA
    {
        For (int i = 0; i <= n; i++) d[i] = INF;
        Memset(inq, 0, sizeof(inq));
        d[s] = 0; inq[s] = true; p[s] = 0; a[s] = INF;

        Queue<int> Q;
        Q.push(s);
        While (!Q.empty())
        {
            Int u = Q.front(); Q.pop();
            Inq[u] = 0;
            For (int i = 0; i < G[u].size(); i++)
            {
                Edge& e = edges[G[u][i]];
                If (e.cap > e.flow && d[e.to] > d[u] + e.cost)
                {
                    d[e.to] = d[u] + e.cost;
                    p[e.to] = G[u][i];
                    a[e.to] = min(a[u], e.cap - e.flow);
                    If (!inq[e.to]) { Q.push(e.to); inq[e.to] = true; }
                }
            }
        }
        If (d[t] == ​​INF) return false;
        Flow += a[t];
        Cost += (long long)d[t] * (long long)a[t];
        For (int u = t; u != s; u = edges[p[u]].from)
        {
            Edges[p[u]].flow += a[t];
            Edges[p[u]^1].flow -= a[t];
        }
        Return true;
    }

    Int MinCostMaxFlow(int s, int t, long long& cost)
    {
        Int flow = 0; cost = 0;
        While (BellmanFord(s, t, flow, cost));
        Return flow;
    }

}solve;

Int n, m, k;
Vector<Edge> IN;

Int main()
{
    Scanf("%d%d%d", &n, &m, &k);
    For (int i = 0; i < m; i++)
    {
        Int u, v, c, w; scanf("%d%d%d%d", &u, &v, &c, &w);
        IN.push_back(Edge(u, v, c, 0, w));
    }

    Int s = 1, t = n;
    Solve.init(t);
    For (int i = 0; i < m; i++) solve.AddEdge(IN[i].from, IN[i].to, IN[i].cap, 0);
    Long long cost1 = 0;
    Int MaxFlow1 = solve.MinCostMaxFlow(s, t, cost1);

    s = 0;
    solve.AddEdge(s, 1, k, 0);
    For (int i = 0; i < m; i++) solve.AddEdge(IN[i].from, IN[i].to, INF, IN[i].cost);
    Long long cost2 = 0;
    Int MaxFlow2 = solve.MinCostMaxFlow(s, t, cost2);
    Printf("%d %lld\n", MaxFlow1, cost2);
    Return 0;
}

/*
5 8 2
1 2 5 8
2 5 9 9
5 1 6 2
5 1 1 8
1 2 8 7
2 5 4 9
1 2 1 1
1 4 2 1
*/