【总结】最小费用流

• 最小费用流就是在保证流量$F$的前提下，求解最少花费是多少的问题${O\_O}$
• 建图: 每条边在最大流基础上$\left(to指向点,cap容量,rev反向边\right)$，增加一个费用$\left(cost\right)$
• 求解方法: 在最大流中，是按照任意可行路径，也就是残余网络中的可增广路径，向网络中注入流量，从而在汇点获得相应流量的策略进行，直到不存在可增广路。简单分析后可以知道:
  
  • 如果原图的最大流$F'<F$，则显然不存在所谓最小费用最大流
  • 将边的费用看做边连接两点的距离，那么如果存在两条流量相同的可增广路径$S_1$和$S_2$$\left({flow}_1={flow}_2\right)$，并且二者的路径长度(也即路径上所有边的费用和)满足 $$\left({Distance}_1<{Distance}_2\right)$$ 那么显然前者是更优的选择。反之亦然，即费用相同时流量越大越好。于是可贪心选取。
  • 为什么不用担心上述贪心会导致: 由于选择了更大流量的路径而影响后面的贪心错误呢？原因就和基于增广路算法的最大流一样啦，窝们不是加了反向边么$t\_t$
• 基于上述求解方法的思路，窝们只需要每次从源点$Source$向汇点$Destination$选择最短路然后增广其可容纳的最大流量即可。
• 复杂度相关: 如果采用$Bellman\dot\ Ford$求最短路，每次获得的最少流量为$1$，于是复杂度为$O\left(F*|V|*|E| \right)$，堆优化的$Dijstra$可以做到$O\left(F*|E|*\log|V|\right)$。但$Bellman$可以处理负权边，也就是可以处理费用为负值的图
• 似乎理解了上述，便足够了，不过还是放两份分别用$Dijstra$和$Bellman$实现的模板，前者还加入了一个有用的顶点势标记来处理负权环.
• 模板1

/* **********************************************

  File Name: min_cost_flow.cpp

  Auther: zhengdongjian@tju.edu.cn

  Created Time: 2015年08月05日 星期三 13时06分05秒

*********************************************** */
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <sstream>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

const double EPS = 1e-8;
const double PI = acos(-1.0);
typedef pair<int, int> P;

const int INF = 0xfffffff;
const int MAX = 10007;
struct Edge
{
    int to;
    int cap;
    int cost;
    int rev;
};
int V; //[0, V)
vector<Edge> G[MAX];
int h[MAX]; //顶点的势
int dist[MAX]; //min_distance
int prevv[MAX]; //前驱
int preve[MAX]; //前驱对应边

inline void add_edge(int from, int to, int cap, int cost)
{
    G[from].push_back((struct Edge){to, cap, cost, (int)G[to].size()});
    G[to].push_back((struct Edge){from, 0, -cost, (int)G[from].size() - 1});
}

int min_cost_flow(int s, int t, int f)
{
    int res = 0;
    memset(h, 0, sizeof(h));
    while (f > 0)
    {
        priority_queue<P, vector<P>, greater<P> > Q;
        fill(dist, dist + V, INF);
        dist[s] = 0;
        Q.push(P(dist[s], s));

        while (!Q.empty())
        {
            P p = Q.top();
            Q.pop();

            int v = p.second;
            if (dist[v] < p.first) continue;
            for (int i = 0; i < (int)G[v].size(); ++i)
            {
                Edge& e = G[v][i];
                if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to])
                {
                    dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                    prevv[e.to] = v;
                    preve[e.to] = i;
                    Q.push(P(dist[e.to], e.to));
                }
            }
        }

        if (dist[t] == INF)
        {
            return -1; //no more route to go
        }

        for (int v = 0; v < V; ++v)
        {
            h[v] += dist[v];
        }

        int d = f;
        for (int v = t; v != s; v = prevv[v])
        {
            d = min(d, G[prevv[v]][preve[v]].cap);
        }
        f -= d;
        res += d * h[t];
        for (int v = t; v != s; v = prevv[v])
        {
            Edge& e = G[prevv[v]][preve[v]];
            e.cap -= d;
            G[v][e.rev].cap += d;
        }
    }
    return res;
}

int main()
{
    return 0;
}

• 模板2

/* **********************************************

  File Name: min_cost_flow_bellman.cpp

  Auther: zhengdongjian@tju.edu.cn

  Created Time: 2015年08月05日 星期三 14时29分57秒

*********************************************** */
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <sstream>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

const double EPS = 1e-8;
const double PI = acos(-1.0);
typedef pair<int, int> P;

const int INF = 0xfffffff;
const int MAX = 10007;
struct Edge
{
    int to;
    int cap;
    int cost;
    int rev;
};
int V; //[0, V)
vector<Edge> G[MAX];
int dist[MAX]; //min_distance
int prevv[MAX]; //前驱
int preve[MAX]; //前驱对应边

inline void add_edge(int from, int to, int cap, int cost)
{
    G[from].push_back((struct Edge){to, cap, cost, (int)G[to].size()});
    G[to].push_back((struct Edge){from, 0, -cost, (int)G[from].size() - 1});
}

int min_cost_flow(int s, int t, int f)
{
    int res = 0;
    while (f > 0)
    {
        fill(dist, dist + V, INF);
        dist[s] = 0;
        bool update = true;
        while (update)
        {
            update = false;
            for (int v = 0; v < V; ++v)
            {
                if (dist[v] == INF) continue;
                for (int i = 0; i < (int)G[v].size(); ++i)
                {
                    Edge& e = G[v][i];
                    if (e.cap > 0 && dist[e.to] > dist[v] + e.cost)
                    {
                        dist[e.to] = dist[v] + e.cost;
                        prevv[e.to] = V;
                        preve[e.to] = i;
                        update = true;
                    }
                }
            }
        }

        if (dist[t] == INF)
        {
            return -1; //no more route to go
        }

        for (int v = 0; v < V; ++v)
        {
            h[v] += dist[v];
        }

        int d = f;
        for (int v = t; v != s; v = prevv[v])
        {
            d = min(d, G[prevv[v]][preve[v]].cap);
        }
        f -= d;
        res += d * dist[t];
        for (int v = t; v != s; v = prevv[v])
        {
            Edge& e = G[prevv[v]][preve[v]];
            e.cap -= d;
            G[v][e.rev].cap += d;
        }
    }
    return res;
}

int main()
{
    return 0;
}