Problem: Examples

Input

4 5 2
0 1 2 1
0 2 1 2
1 2 1 1
1 3 1 3
2 3 2 1


Output

6


Input




Output

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

const int INF = 1<<30;

typedef struct{
    int to, cap, cost, rev;
}Edge;

class MinCostFlow{
private:
    int V;
    vector<vector<Edge>> G;
public:
    MinCostFlow(int V): V(V){
        G.resize(V);
    }
    void add_edge(int u, int v, int c, int d){
        G[u].push_back({v, c, d, (int)G[v].size()});
        G[v].push_back({u, 0, -d, (int)G[u].size()-1});
    }
    int solve(int s, int t, int f){
        int res = 0;
        while(f > 0){
            vector<int> d(V, INF);
            vector<int> pars(V, -1);
            vector<int> eids(V, -1);
            d[s] = 0;
            
            bool updated = true;
            while(updated){
                updated = false;
                for(int v=0; v<V; v++) if(d[v]!=INF){
                    for(int i=0; i<G[v].size(); i++){
                        auto edge = G[v][i];
                        if(edge.cap == 0)
                            continue;
                        if(d[edge.to] > d[v] + edge.cost){
                            d[edge.to] = d[v] + edge.cost;
                            pars[edge.to] = v;
                            eids[edge.to] = i;
                            updated = true;
                        }
                    }
                }
            }
            if(d[t] == INF)
                return -1;
            
            int mc = f;
            for(int v=t; v!=s; v=pars[v]){
                mc = min(mc, G[pars[v]][eids[v]].cap);
            }
            res += mc * d[t];
            f -= mc;
            for(int v=t; v!=s; v=pars[v]){
                auto &edge = G[pars[v]][eids[v]];
                edge.cap -= mc;
                G[v][edge.rev].cap += mc;
            }
        }
        return res;
    }
};

int V, E, F;

int main(){
    cin >> V >> E >> F;
    
    MinCostFlow mcf(V);
    for(int i=0; i<E; i++){
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        mcf.add_edge(u, v, c, d);
    }
    
    cout << mcf.solve(0, V-1, F) << endl;
    
    return 0;
}