最小費用フローテンプレート

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace std;



 



class mincost

{

private:

    const static int V = 1001;

    const static int E = 1000001;

    const static int INF = -1u >> 1;



    struct Edge

    {

        int v, cap, cost;

        Edge *next;

    } pool[E], *g[V], *pp, *pree[V];

    int T, S, dis[V], pre[V];

    int n, m, flow, cirq[V];

    void SPFA();

    inline void addedge(int i, int j, int cap, int cost);

public:

    bool initialize();

    void mincost_maxflow();

};



void mincost::mincost_maxflow()

{

    while (true)

    {

        SPFA();

        if (dis[T] == INF)

            break;

        int minn = INF;

        for (int i = T; i != S; i = pre[i])

            minn = min(minn, pree[i]->cap);

        for (int i = T; i != S; i = pre[i])

        {

            pree[i]->cap -= minn;

            pool[(pree[i] - pool)^0x1].cap += minn;

            flow += minn * pree[i]->cost;

        }

    }

    printf("%d
", flow);

}



void mincost::SPFA()

{

    bool vst[V] = {false};

    int tail = 0, u;

    fill(dis,dis + n,0x7fffffff);

    cirq[0] = S;

    vst[S] = 1;

    dis[S] = 0;

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

    {

        int v = cirq[i % n];

        for (Edge *i = g[v]; i != NULL; i = i->next)

        {

            if (!i->cap)

                continue;

            u = i->v;

            if (i->cost + dis[v] < dis[u])

            {

                dis[u] = i->cost + dis[v];

                pree[u] = i;

                pre[u] = v;

                if (!vst[u])

                {

                    tail++;

                    cirq[tail % n] = u;

                    vst[u] = true;

                }

            }

        }

        vst[v] = false;

    }

}



void mincost::addedge(int i, int j, int cap, int cost)

{

    pp->cap = cap;

    pp->v = j;

    pp->cost = cost;

    pp->next = g[i];

    g[i] = pp++;

}



bool mincost::initialize()

{

    memset(g, 0, sizeof (g));

    pp = pool;

    scanf("%*s %*d");

    scanf("%d %d %d %d", &n, &m, &S, &T);

    int v, u, f, c;

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

    {

        scanf("%d %d %d %d", &v, &u, &f, &c);

        addedge(v, u, f, c);

        addedge(u, v, 0, -c);

    }

    flow = 0;

    return true;

}

mincost g;



int main()

{

    int t;

    scanf("%d", &t);

    while (t--)

    {

        g.initialize();

        g.mincost_maxflow();

    }

    return 0;

}