算法思想

在最小费用最大流中，网络中需要考虑的不仅是流量了，还涉及到单位流量流过的费用，网络流的费用成为了每条边的流量×单位流量的费用，即 $Cost(flow)=\sum_{<x,y>\in E}cost(x,y)×flow(x,y)$ ，求解最小费用最大流有两个思路

先找最小单位费用路，之后在该路径上增流并增加到最大流，最小费用路算法
先找最大流，然后找负费用圈，消减费用，减少到最小费用，消圈算法

最小费用路算法

最小费用路算法是寻找源点到汇点的最小费用路，也就是以费用为边权，找最短路，然后对找到的最短路进行增流，以此反复，需要注意的是，在求解最大流时，最短增广路算法中的最短增广路是去权值的最短路，而最小费用路是以单位费用为权值的最短路，一般分成求出最小费用路和沿最小费用路增流，可以选用SPFA+EK=MCMF的方式，这种方式便于处理负权边，也可以采用Dijkstra+Dinic/ISAP，但一般由于负权边的关系，采用MCMF较多，下面给出模板

代码（MCMF）

bool SPFA(int s,int t) {
    queue<int>q;
    memset(vis,0,sizeof(vis));
    memset(pre,-1,sizeof(pre));
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    vis[s]=1;
    q.push(s);
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u]; ~i; i=e[i].next) {
            int v=e[i].to;
            if(e[i].cap>e[i].flow&&dis[v]>dis[u]+e[i].pay) {
                dis[v]=dis[u]+e[i].pay;
                pre[v]=i;
                if(vis[v])continue;
                vis[v]=1;
                q.push(v);
            }
        }
    }
    return pre[t]!=-1;
}
int MCMF(int s,int t) {
    int mincost=0;
    while(SPFA(s,t)) {
        int d=inf,v=t;
        while(v!=s) {
            int i=pre[v];
            d=min(d,e[i].cap-e[i].flow);//可增加的流量
            v=e[i^1].to;//换点
        }
        v=t;
        while(v!=s) {
            int i=pre[v];
            e[i].flow+=d;
            e[i^1].flow-=d;//实流
            v=e[i^1].to;
        }
        mincost+=dis[t]*d;
    }
    return mincost;
}

消圈算法

MCMF方便求最优解，但是如果求的不是最优解，或者只是求出比当前方案更好的更优解，消圈算法就更好一些，对一个网络来说，如果已经求得最小费用路，那么其对应的缓和网络中是没有负费用圈的，如果有负费用圈，那么一定可以沿着这个圈继续增广，得到相同费用下更小的流，即最小费用流等价残余网络中无负费用圈
可以采用SPFA先判断是否有费用圈，之后再通过回溯找到负费用圈，然后增流

代码

int negative_loop(int s,int t) {
    int f,r,top=-1;
    f=0;
    r=-1;
    memset(num,0,sizeof(num));
    memset(dist,0,sizeof(dist));
    memset(vis,true,sizeof(vis));//inq是bool类型的数组，每个元素占1字节，所以可以这样
    memset(pre,-1,sizeof(pre));
    for(int i=s; i<=t; i++)
        q[++r]=i;
    while(f<=r) {
        int u=q[r--];//栈式写法，r--改成f++就是队列了，队列要将数组扩大。
        vis[u]=false;//实际测试中，用栈比队列判断负圈效率更高
        for(int i=head[u]; ~i; i=E[i].next) {
            int v=E[i].v;
            if(E[i].cap>E[i].flow&&dist[v]>dist[u]+E[i].cost) { //松弛操作
                dist[v]=dist[u]+E[i].cost;
                pre[v]=i; //记录前驱
                if(!vis[v]) { //顶点v不在队内
                    q[++r]=v;
                    vis[v]=true; //标记
                    if(++num[v]>t+1)
                        return v;
                }
            }
        }
    }
    return -1;
}
 for(int i=pre[k]; !vis[E[i].v]; i=pre[E[i^1].v]) { //往前找负环
            vis[E[i].v]=true;
            k=E[i].v;
        }
        for(int i=pre[k];; i=pre[E[i^1].v]) { //在负环中增加1个流量
            E[i].flow++;
            E[i^1].flow--;
            if(E[i^1].v==k) break;
        }

训练

POJ2135

题目大意： $N$ 个节点的无向图，无环，无重边，编号 $1$ ~ $N$ ，起点为1，中转站为N，有M条边，有边权，现在要从起点到中转站再到起点，求保证不会经过重复边的前提下的所走的最小长度

思路：设置边的容量为1，由于每条边只能走一次，但是需要从1到N再回来，可以看做存在从1到N有两条不同的路径，也就是流量为2，将边权看做费用，那么问题就转换为求最小费用最大流，添加源点和汇点，对每一条边，由于两边都可以走，没有指向，所以要加双向边，加残余网络边时费用为负值，因此不适合用Dijkstra+Dinic/ISAP

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1e3+10;
int head[maxn],cnt,dis[maxn],n,m,pre[maxn];
bool vis[maxn];
struct node {
    int to,next,cap,flow,pay;
} e[maxn*80];
void Add(int from,int to,int cap,int flow,int pay) {
    e[cnt].to=to;
    e[cnt].next=head[from];
    e[cnt].cap=cap;
    e[cnt].flow=flow;
    e[cnt].pay=pay;
    head[from]=cnt++;
}
bool SPFA(int s,int t) {
    queue<int>q;
    memset(vis,0,sizeof(vis));
    memset(pre,-1,sizeof(pre));
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    vis[s]=1;
    q.push(s);
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u]; ~i; i=e[i].next) {
            int v=e[i].to;
            if(e[i].cap>e[i].flow&&dis[v]>dis[u]+e[i].pay) {
                dis[v]=dis[u]+e[i].pay;
                pre[v]=i;
                if(vis[v])continue;
                vis[v]=1;
                q.push(v);
            }
        }
    }
    return pre[t]!=-1;
}
int MCMF(int s,int t) {
    int mincost=0;
    while(SPFA(s,t)) {
        int d=inf,v=t;
        while(v!=s) {
            int i=pre[v];
            d=min(d,e[i].cap-e[i].flow);//可增加的流量
            v=e[i^1].to;//换点
        }
        v=t;
        while(v!=s) {
            int i=pre[v];
            e[i].flow+=d;
            e[i^1].flow-=d;//实流
            v=e[i^1].to;
        }
        mincost+=dis[t]*d;
    }
    return mincost;
}

using namespace std;
int main() {
    scanf("%d%d",&n,&m);
    int s=0,t=n+1;
    memset(head,-1,sizeof(head));
    while(m--) {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        Add(u,v,1,0,w);//建双向边，两边都可以走
        Add(v,u,0,0,-w);
        Add(v,u,1,0,w);
        Add(u,v,0,0,-w);
    }
    Add(s,1,2,0,0);//连接源点
    Add(1,s,0,0,0);
    Add(n,n+1,2,0,0);//连接汇点
    Add(n+1,n,0,0,0);
    cout <<MCMF(s,t);
    return 0;
}

LuoguP2770

题目大意：略

思路：这一道题和POJ2135有些类似，但题目中有很关键的话：从西向东和从东到西，也就是说，在走的过程中，除了有所有城市只能访问一次（除起点），还有一个约束，从起点到中转的路径必须是递增，从中转到起点的路径，必须是递减，这一点就约束了不能建图时无脑建双边，将点拆成边，源点和汇点的边容量为2，假定边的方向是编号低向编号高，由于需要有来有回，问题被转换成源点到汇点的最小费用最大流问题，需要满足最大流为2，求一个来回的问题被转换成求两个路径
在建图时，如果给定边正好是源点和汇点，该边的边容量为2，为了获得最多城市，只需要将费用1取反，求最短路，则必然负数最多，对应城市最多
输出答案，此时网络中应该存在两条路径，从源点出发，沿着增流且花费为负的方向走，并标记已经经过的点，到终点后，代表已经有一条路径找到了，之后继续向起点走，沿着减流且花费为正的方向走，因为减流且花费为负代表其正向边增流且花费为负，正好对应另一条路径

代码

#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=2e4+10;
int n,m,head[maxn],cnt,dis[maxn],pre[maxn],s,t,mincost;
bool vis[maxn];
unordered_map<string,int>Umap;
string Dic[maxn];
struct node {
    int next,to,cap,flow,pay;
} e[maxn];
void Add(int from,int to,int cap,int flow,int pay) {
    e[cnt].cap=cap;
    e[cnt].flow=flow;
    e[cnt].to=to;
    e[cnt].pay=pay;
    e[cnt].next=head[from];
    head[from]=cnt++;
}
bool SPFA(int s,int t) {
    queue<int>q;
    memset(vis,0,sizeof(vis));
    memset(pre,-1,sizeof(pre));
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    vis[s]=1;
    q.push(s);
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u]; ~i; i=e[i].next) {
            int v=e[i].to;
            if(e[i].cap>e[i].flow&&dis[v]>dis[u]+e[i].pay) {
                dis[v]=dis[u]+e[i].pay;
                pre[v]=i;
                if(vis[v])continue;
                vis[v]=1;
                q.push(v);
            }
        }
    }
    return pre[t]!=-1;
}
int MCMF(int s,int t) {
    int maxflow=0;
    while(SPFA(s,t)) {
        int d=inf,v=t;
        while(v!=s) {
            int i=pre[v];
            d=min(d,e[i].cap-e[i].flow);//可增加的流量
            v=e[i^1].to;//换点
        }
        v=t;
        maxflow+=d;
        while(v!=s) {
            int i=pre[v];
            e[i].flow+=d;
            e[i^1].flow-=d;//实流
            v=e[i^1].to;
        }
        mincost+=dis[t]*d;
    }
    return maxflow;
}
void DFS(int u) {
    vis[u]=1;
    for(int i=head[u]; ~i; i=e[i].next) {
        int v=e[i].to;
        if(vis[v])continue;
        if((e[i].flow>0&&e[i].pay<=0)||(e[i].flow<0&&e[i].pay>=0)) {
            DFS(v);//先搜后输出，输出的顺序和搜索是相反的，但是根据题意也符合
            if(v<=n)cout <<Dic[v]<<endl;
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>n>>m;
    s=1,t=2*n;
    memset(head,-1,sizeof(head));
    for(int i=1; i<=n; i++)//拆点
        if(i==1||i==n) {//如果是源点或者汇点，边容量为2
            Add(i,i+n,2,0,0);
            Add(i+n,i,0,0,0);
        } else {
            Add(i,i+n,1,0,0);
            Add(i+n,i,0,0,0);
        }
    for(int i=1; i<=n; i++) {
        string str;
        cin >>str;
        Umap[str]=i;//哈希
        Dic[i]=str;//索引
    }
    while(m--) {
        string x,y;
        cin >>x>>y;
        int xx=Umap[x],yy=Umap[y];
        if(xx<yy) {
            if(xx==1&&yy==n)//如果正好是源点和汇点，边容量就为2
                Add(xx+n,yy,2,0,-1);//求点最多，费用为负，便于求最短路
            else
                Add(xx+n,yy,1,0,-1);
            Add(yy,xx+n,0,0,1);
        } else {
            if(yy==1&&xx==n) Add(yy+n,xx,2,0,-1);
            else Add(yy+n,xx,1,0,-1);
            Add(xx,yy+n,0,0,1);
        }
    }
    if(MCMF(s,t)==2) {
        cout <<-mincost<<endl;
        cout <<Dic[1]<<endl;
        memset(vis,0,sizeof(vis));
        DFS(1);
        cout <<Dic[1]<<endl;
    } else
        cout <<"No Solution!"<<endl;
    return 0;
}

POJ3680

题目大意：给出n个加权开区间，第 $i$ 个区间覆盖 $a_i,b_i)$ ，权值为 $w_i$ ，选择一些区间使得整个数轴没有点的覆盖数超过 $k$ 的情况下，使总权值最大

思路：总权值最大，那么费用用负值，对于所有的区间短点，需要先离散化，然后设置源点汇点，对于每个区间，左端点到右端点连一条边，容量为1，代表只能选一次，相邻的端点间 $i$ 到 $i + 1$ 连接一条边，容量为k，求最小费用最大流即可

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=4e5+10;
int n,k,T,s,t,cnt,head[405],l[205],r[205],w[205],ans,num[405],dis[405],pre[405];
bool vis[405];
struct node {
    int next,to,cap,flow,pay;
} e[maxn];
void Add(int from,int to,int cap,int flow,int pay) {
    e[cnt].cap=cap;
    e[cnt].to=to;
    e[cnt].flow=flow;
    e[cnt].next=head[from];
    e[cnt].pay=pay;
    head[from]=cnt++;
}
bool SPFA(int s,int t) {
    queue<int>q;
    memset(vis,0,sizeof(vis));
    memset(pre,-1,sizeof(pre));
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    vis[s]=1;
    q.push(s);
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u]; ~i; i=e[i].next) {
            int v=e[i].to;
            if(e[i].cap>e[i].flow&&dis[v]>dis[u]+e[i].pay) {
                dis[v]=dis[u]+e[i].pay;
                pre[v]=i;
                if(vis[v])continue;
                vis[v]=1;
                q.push(v);
            }
        }
    }
    return pre[t]!=-1;
}
int MCMF(int s,int t) {
    int mincost=0;
    while(SPFA(s,t)) {
        int d=inf,v=t;
        while(v!=s) {
            int i=pre[v];
            d=min(d,e[i].cap-e[i].flow);//可增加的流量
            v=e[i^1].to;//换点
        }
        v=t;
        while(v!=s) {
            int i=pre[v];
            e[i].flow+=d;
            e[i^1].flow-=d;//实流
            v=e[i^1].to;
        }
        mincost+=dis[t]*d;
    }
    return mincost;
}
int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&k);
        cnt=ans=0;
        memset(head,-1,sizeof(head));
        for(int i=1; i<=n; i++) {//记录区间，并存储端点用于离散化
            scanf("%d%d%d",l+i,r+i,w+i);
            num[++ans]=l[i],num[++ans]=r[i];
        }
        sort(num+1,num+ans+1);//排序
        ans=unique(num+1,num+ans+1)-num-1;//去重
        s=0,t=ans+1;
        for(int i=0; i<=ans; i++) {//设置容量，代表点最多经过k次
            Add(i,i+1,k,0,0);
            Add(i+1,i,0,0,0);
        }
        for(int i=1; i<=n; i++) {
            int u=lower_bound(num+1,num+ans+1,l[i])-num;//获得离散化坐标
            int v=lower_bound(num+1,num+ans+1,r[i])-num;
            Add(u,v,1,0,-w[i]);
            Add(v,u,0,0,w[i]);
        }
        cout <<-MCMF(s,t)<<endl;
    }
    return 0;
}

POJ2175

题目大意：略

思路：如果一开始盲目的求最优解的话一定会超时，可以计算一下复杂度， $M C M F$ 的复杂度为 $O(VE^2)$ ，而在本题目中，复杂度的表达式为 $O((N+2)×(N×M+N+M)^2)≈O(N^5)$ ，带入100，显然时间过大，那么，我们需要在给出解的基础上判断是否存在更优的解即可，那么先构造出原题给出的方案，如果直接跑MCMF是不行的，因为存在负环，SPFA会死循环，这个时候就需要消圈算法，如果给出的解是最优解，那么构造出的混合网络就没有负费用圈，如果有，则沿着负费用圈增广，就可以得到费用更小的流，用SPFA判断是否存在负环，然后找到通过次数过多的点，但是该点未补在负环中，负环在这个点之前，找到负环即可

代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=205;
const int M=40410;
int cnt;
int head[N],dist[N],pre[N];//dist[i]表示源点到点i最短距离，pre[i]记录前驱
bool vis[N];//标记数组
int G[N][N],q[N],num[N],shelter[N];
struct node {
    int x,y,p;
} a[N],b[N];

struct Edge {
    int v,next;
    int cap,flow,cost;
} E[M<<1];

void init() { //初始化
    memset(head,-1,sizeof(head));
    cnt=0;
}

void add(int u,int v,int c,int cost,int flow) {
    E[cnt].v=v;
    E[cnt].cap=c;
    E[cnt].flow=flow;
    E[cnt].cost=cost;
    E[cnt].next=head[u];
    head[u]=cnt++;
}

void adde(int u,int v,int c,int cost,int flow) {
    add(u,v,c,cost,flow);
    add(v,u,0,-cost,-flow);
}

int negative_loop(int s,int t) {
    int f,r,top=-1;
    f=0;
    r=-1;
    memset(num,0,sizeof(num));
    memset(dist,0,sizeof(dist));
    memset(vis,true,sizeof(vis));//inq是bool类型的数组，每个元素占1字节，所以可以这样
    memset(pre,-1,sizeof(pre));
    for(int i=s; i<=t; i++)
        q[++r]=i;
    while(f<=r) {
        int u=q[r--];//栈式写法，r--改成f++就是队列了，队列要将数组扩大。
        vis[u]=false;//实际测试中，用栈比队列判断负圈效率更高
        for(int i=head[u]; ~i; i=E[i].next) {
            int v=E[i].v;
            if(E[i].cap>E[i].flow&&dist[v]>dist[u]+E[i].cost) { //松弛操作
                dist[v]=dist[u]+E[i].cost;
                pre[v]=i; //记录前驱
                if(!vis[v]) { //顶点v不在队内
                    q[++r]=v;
                    vis[v]=true; //标记
                    if(++num[v]>t+1)
                        return v;
                }
            }
        }
    }
    return -1;
}

int dis(node p1,node p2) { //曼哈顿距离+1
    return abs(p1.x-p2.x)+abs(p1.y-p2.y)+1;
}

int main() {
    int n,m,s,t,p;
    scanf("%d%d",&n,&m);
    s=0,t=n+m+1;
    init();
    for(int i=0; i<n; i++) { //读入大楼位置人数
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].p);
        adde(s,i+1,a[i].p,0,a[i].p);//源点到大楼，容量a[i].p，费用0，流量a[i].p
    }
    for(int j=0; j<m; j++) //读入防空洞位置人数
        scanf("%d%d%d",&b[j].x,&b[j].y,&b[j].p);
    memset(shelter,0,sizeof(shelter));
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++) {
            scanf("%d",&p);
            shelter[j]+=p;
            adde(i+1,n+j+1,inf,dis(a[i],b[j]),p);//大楼到防空洞,容量inf，费用两者曼哈顿距离+1，流量p
        }
    for(int j=0; j<m; j++)
        adde(n+j+1,t,b[j].p,0,shelter[j]);//防空洞到汇点，容量b[i].p，费用0，流量shelter[i]
    int k=negative_loop(s,t);
    if(k!=-1) {
        printf("SUBOPTIMAL\n");
        memset(vis,0,sizeof(vis));
        memset(G,0,sizeof(G));
        for(int i=pre[k]; !vis[E[i].v]; i=pre[E[i^1].v]) { //往前找负环
            vis[E[i].v]=true;
            k=E[i].v;
        }//因为是环，会找到一个点被访问两次
        for(int i=pre[k];; i=pre[E[i^1].v]) { //在负环中增加1个流量
            E[i].flow++;
            E[i^1].flow--;
            if(E[i^1].v==k) break;
        }
        for(int i=0; i<cnt; i++) 
            if(E[i^1].v>0&&E[i^1].v<=n&&E[i].v>n&&E[i].v<=n+m)
                G[E[i^1].v-1][E[i].v-n-1]=E[i].flow;
        for(int i=0; i<n; i++) { //输出结果
            for(int j=0; j<m; j++) {
                if(j) printf(" ");
                printf("%d",G[i][j]);
            }
            printf("\n");
        }
    } else
        printf("OPTIMAL\n");
    return 0;
}

代码（求最优解）

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=2e4+10;
int n,m,s,t,cnt,head[121],dis[121],pre[121],ans,graph[121][121];
bool vis[121];
struct build {
    int x,y,c;
} b[212];
int Dist(build a,build b) {
    return abs(a.x-b.x)+abs(a.y-b.y)+1;
}
struct node {
    int next,to,cap,flow,pay;
} e[maxn];
void Add(int from,int to,int cap,int flow,int pay) {
    e[cnt].cap=cap;
    e[cnt].to=to;
    e[cnt].flow=flow;
    e[cnt].next=head[from];
    e[cnt].pay=pay;
    head[from]=cnt++;
}
bool SPFA(int s,int t) {
    queue<int>q;
    memset(vis,0,sizeof(vis));
    memset(pre,-1,sizeof(pre));
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    vis[s]=1;
    q.push(s);
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u]; ~i; i=e[i].next) {
            int v=e[i].to;
            if(e[i].cap>e[i].flow&&dis[v]>dis[u]+e[i].pay) {
                dis[v]=dis[u]+e[i].pay;
                pre[v]=i;
                if(vis[v])continue;
                vis[v]=1;
                q.push(v);
            }
        }
    }
    return pre[t]!=-1;
}
int MCMF(int s,int t) {
    int mincost=0;
    while(SPFA(s,t)) {
        int d=inf,v=t;
        while(v!=s) {
            int i=pre[v];
            d=min(d,e[i].cap-e[i].flow);//可增加的流量
            v=e[i^1].to;//换点
        }
        v=t;
        while(v!=s) {
            int i=pre[v];
            e[i].flow+=d;
            e[i^1].flow-=d;//实流
            v=e[i^1].to;
        }
        mincost+=dis[t]*d;
    }
    return mincost;
}
int main() {
    int cost=0;
    scanf("%d%d",&n,&m);
    s=0,t=n+m+1;
    memset(head,-1,sizeof(head));
    for(int i=1; i<=n; i++)
        scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].c);
    for(int i=n+1; i<=n+m; i++)
        scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].c);
    for(int i=1; i<=n; i++)
        for(int j=n+1; j<=n+m; j++) {
            int num=0;
            scanf("%d",&num);
            cost+=Dist(b[i],b[j])*num;
        }
    for(int i=1; i<=n; i++)
        for(int j=n+1; j<=n+m; j++) {
            Add(i,j,inf,0,Dist(b[i],b[j]));
            Add(j,i,0,0,-Dist(b[i],b[j]));
        }
    for(int i=1; i<=n; i++) {
        Add(s,i,b[i].c,0,0);
        Add(i,s,0,0,0);
    }
    for(int i=n+1; i<=n+m; i++) {
        Add(i,t,b[i].c,0,0);
        Add(t,i,0,0,0);
    }
    if(MCMF(s,t)==cost)
        printf("OPTIMAL\n");
    else {
        printf("SUBOPTIMAL\n");
        for(int u=1; u<=n; u++)
            for(int i=head[u]; ~i; i=e[i].next) {
                int v=e[i].to;
                if(e[i].flow>=0&&v!=s)
                    graph[u][v-n]=e[i].flow;
            }
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++)
                printf("%d%c",graph[i][j],j==m?'\0':' ');
            putchar('\n');
        }
    }
    return 0;
}

UVA11613

题目大意：略

思路：首先，本题需要注意到一点，每个月有最大生产量，但是，并不是一定要生产这么多，如果计算出来会亏本，那不如不生产，其次，本题需要拆点，一个作为生产专用，一个作为销售专用，源点与对应点相连，容量为产量，费用为成本，对应拆点与汇点连接，容量为销售量，费用为售价负值，最后，由于存在保质期，那么每个点与对应的保质期内的销售节点相连，容量为产量，费用为储存值×月数

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=4e4+5;
const int inf=0x3f3f3f3f;
const int N=405;
int T,m,load,s,t,pre[N],head[N],cnt;
int price[N],month[N],dis[N],mxp[N];
bool vis[N];
struct node {
    int to,next,cap,flow,pay;
} e[maxn];
void Add(int from,int to,int cap,int flow,int pay) {
    e[cnt].to=to;
    e[cnt].cap=cap;
    e[cnt].flow=flow;
    e[cnt].pay=pay;
    e[cnt].next=head[from];
    head[from]=cnt++;
}
bool SPFA(int s,int t) {
    queue<int>q;
    memset(vis,0,sizeof(vis));
    memset(pre,-1,sizeof(pre));
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    vis[s]=1;
    q.push(s);
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u]; ~i; i=e[i].next) {
            int v=e[i].to;
            if(e[i].cap>e[i].flow&&dis[v]>dis[u]+e[i].pay) {
                dis[v]=dis[u]+e[i].pay;
                pre[v]=i;
                if(vis[v])continue;
                vis[v]=1;
                q.push(v);
            }
        }
    }
    if(dis[t]>0)return 0;//这一句很重要，如果费用大于0，代表已经亏本了
    return pre[t]!=-1;
}
int MCMF(int s,int t) {
    int mincost=0;
    while(SPFA(s,t)) {
        int d=inf,v=t;
        while(v!=s) {
            int i=pre[v];
            d=min(d,e[i].cap-e[i].flow);//可增加的流量
            v=e[i^1].to;//换点
        }
        v=t;
        while(v!=s) {
            int i=pre[v];
            e[i].flow+=d;
            e[i^1].flow-=d;//实流
            v=e[i^1].to;
        }
        mincost+=dis[t]*d;
    }
    return mincost;
}
signed main() {
    scanf("%lld",&T);
    for(int k=1; k<=T; k++) {
        memset(head,-1,sizeof(head));
        scanf("%lld%lld",&m,&load);
        s=0,t=2*m+1;
        cnt=0;
        for(int i=1; i<=m; i++) {
            int local,mxs;
            scanf("%lld%lld%lld%lld%lld",&local,&mxp[i],&price[i],&mxs,&month[i]);
            Add(s,i,mxp[i],0,local);//源点到i，容量为产量，费用为成本
            Add(i,s,0,0,-local);
            Add(i+m,t,mxs,0,-price[i]);//拆点到汇点，容量为销售量，费用为负售价（求最小）
            Add(t,i+m,0,0,price[i]);
        }
        for(int i=1; i<=m; i++)
            for(int j=0; j<=month[i]; j++) {//保质期前销售
                Add(i,i+m+j,mxp[i],0,j*load);
                Add(i+m+j,i,0,0,-j*load);
            }
        printf("Case %lld: %lld\n",k,-MCMF(s,t));
    }
    return 0;
}

总结

最小费用最大流属于网络流问题，建图仍然是主要的问题，如何将题目给定条件转换成图的边权和点权是最为关键的问题，之后就是套用模板的过程，根据题设条件用对应算法求解

举个例子，如果费用与流量平方成正比，容量 $c a p$ 为整数，每条边有一个费用系数 $a$ ，该边的流量为 $x$ 时边费用为 $ax^2$ ，这时为了求出最小费用流，对于费用为 $ax^2$ 的边，需要将这条边拆了，拆成 $c$ 条容量为1，费用为 $a,3a,\dots (2c-1)a$ 的边，流量为x时，走前x条费用最小的边