网络流拓展——最小费用最大流

最小费用最大流作为最大流的拓展，基本上和找最大流的思路一致。因为费用流需要首先保证所有的流全部被增广，所以找最大流还是主要目的。不过这一次的网络流的每一条边都有自己的权重，那么在建残量网络的时候，原先的bfs就无法适应这个变化。这个时候要保证最小的费用，那么我们就借用最短路的spfa的思路来做。这个时候每一条边的权值就是单位流量。当初我很犯傻的以为是将单位流量和那条边的总流量的乘积作为权值。。为啥不这样干呢？那我们就得这样想：在整个图中如果只有一条增光路，那么费用在一定程度上是一定的。而最小的话就说明有其他的路可走，在总流量一定的情况下，当然是单位的费用越小越好就更优。还有一点就是，由于使用spfa来搜索，那么增光路就不像最大流一样要dfs找，而是一定的，这就需要我们用一个数组来记录。那么怎么存呢？用一个边的数组way[i]来存路径上指向第i个的边。这样在找流时就从t递推回去。还有一点是关于方向边的处理，单位费用在反向边的时候要变成负的，代表退流的时候费用要减去多的那部分。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 10001;
const int maxe = 100001;

struct edge{
    int t,c,w;
    edge* next, *other;
}e[maxe],*head[maxn];
int ne = 0;

void addedge(int f,int t,int c,int w)
{
    e[ne].t = t,e[ne].c = c,e[ne].w = w;
    e[ne].next = head[f];
    head[f] = e + ne++;
    e[ne].t = f,e[ne].c = 0, e[ne].w = -w;
    e[ne].next = head[t];
    head[t] = e+ne++;
    e[ne-1].other = e + ne-2;
    e[ne-2].other = e + ne -1;
}

bool in[maxn];
int dis[maxn];
edge* way[maxn];
int q[maxn];
int l,r;
int n,m;

bool spfa(int s,int t)
{
    memset(q,0,sizeof(q));
    memset(dis,inf,sizeof(dis));
    memset(in,false,sizeof(in));
    for(int i = 1; i <= n; i++)
        way[i] = NULL;
    l = 0,r = 0;
    q[r++] = s;
    dis[s] = 0;
    in[s] = true;
    while(l^r)
    {
        int now = q[l++];
        in[now] = false;
        for(edge* p = head[now];p;p = p->next)
        {
            if(p->c && dis[p->t] > dis[now] + p->w)
            {
                way[p->t] = p;
                dis[p->t] = dis[now] + p->w;
                if(in[p->t] == false) q[r++] = p->t, in[p->t] = true;
            }
        }
    }
    if(dis[t] != inf) return true;
    else return false;
}

int sov(int s,int t)
{
    int minflow,mincost;
    mincost =0 ;
    while(spfa(s,t))
    {
        minflow = inf+1;
        edge* now = way[t];
        while(now)
        {
            minflow = min(minflow,now->c);
            now = way[now->other->t];
        }
        now = way[t];
        while(now)
        {
            now->c -= minflow;
            now->other->c += minflow;
            mincost += minflow * (now->w);
            now = way[now->other->t];
        }
    }
    return mincost;
}

int main()
{
    freopen("cost.in","r",stdin);
    //freopen("cost.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= m; i++)
    {
        int f,t,c,w;
        scanf("%d%d%d%d",&f,&t,&c,&w);
        addedge(f,t,c,w);
    }
    printf("%d
",sov(1,n));
}