P4015 运输问题
@[toc]

题目描述：

在这里插入图片描述

输入格式：

在这里插入图片描述

输出格式：

两行分别输出最小运输费用和最大运输费用。

输入输出样例：

输入 #1

2 3
220 280
170 120 210
77 39 105
150 186 122

输出 #1

48500
69140

题解：

最小费用最大流(MCMF)问题
根据样例数据分析：
橙色为第一个仓库晕倒各零售商店的单位费用
绿色为第二个
在这里插入图片描述
一边是仓库，一边是商店，典型的二分图，还是完全二分图
我们可以在仓库的左边设置一个源点S，右边设置一个终点T。S指向每一个仓库，容量为ai，费用为0，而每一个商店指向T，容量为bi，费用为0
从仓库到商店的边容量是min（仓库货物量ai，商店容量bi），费用为读入的值
为了方便处理，我们可以将S点记为编号1，仓库为编号1 ~ m，商店为m+1 ~ n+m，T点为201
然后直接跑最小费用最大流就可以了
找到最大后，将费用取反再跑一遍即可找到最小

代码：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<algorithm>

#define I_copy_this_answer return 0;

using namespace std;

int n,m,head[1100];
int cnt=1;
int mincost,maxwater;
int flow[1100];
int b[1100],cost[310][310];
int pre[1100],last[1100],dis[1100],vis[1100],a[1100];
int s=0;
//last记录边，pre记录点 
struct node{
    int next,to,dis,flow; 
}edge[100860]; 

void addedge(int next,int to,int dis,int flow)
{
    edge[++cnt].to=to;
    edge[cnt].dis=dis;
    edge[cnt].flow=flow;
    edge[cnt].next=head[next];
    head[next]=cnt;
}


int spfa()
{
    memset(flow,0x3f,sizeof(flow));
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    queue <int> q;
    q.push(s);
    dis[s]=0;
    vis[s]=1;
    pre[201]=-1;  //初始化汇点的前点 
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;

        for(int i=head[u];i;i=edge[i].next)
        {
            int    v=edge[i].to;
            int w=edge[i].dis;
            int l=edge[i].flow;
            if(dis[u]+w<dis[v]&&l>0)  //没有流量的话这条路就增广不了，最短距离是建立在增广路存在的基础上的 
            {
                dis[v]=dis[u]+w;
                last[v]=i;  //last指的是这个点(v)与上个点(u)相连的边的编号 
                pre[v]=u;  //pre指的是这条路径上这个点(v)的上一个点 
                flow[v]=min(flow[u],l);  //把当前边流量与上个点的流量对比，解决出现仓库货物比需要的少的情况 
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return pre[201]!=-1;  //如果不是这个值就说明这个点被刷新，增广成功 
}

void mcmf()
{
    while(spfa())
    {
        mincost+=dis[201]*flow[201];   //从源点出发到汇点的单位费用再乘以单位，由于每次只增广一条路，而且仓库和商店是直接连接的，可以这样写 
        int t=201;
        while(t!=0)
        {
            edge[last[t]].flow-=flow[201];  //回溯，修改每条边的流量，因为该算法中途找到的增广路不是最后的增广路，所以这个要等到最后来改变 
            edge[last[t]^1].flow+=flow[201];
            t=pre[t];
        }
    }
}

void build_edge(int t)//t用来控制边权的正负，为了方便求最小和最大 
{

    for(int i=1;i<=m;i++)
    {
        addedge(0,i,0,a[i]);
        addedge(i,0,0,0);//与源点S相连 
    } 
    for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)
    {
        addedge(i,j+m,cost[i][j]*t,b[j]);
        addedge(j+m,i,-cost[i][j]*t,0);//仓库与商店相连 
    }
    for(int i=1;i<=n;i++)
    {
        addedge(i+m,201,0,b[i]);//与汇点T相连 
        addedge(201,i+m,0,0);
    }
}

int main()
{
    int i,j;
    scanf("%d %d",&m,&n);
    for(i=1;i<=m;i++)
    {
        int t1;
        scanf("%d",&a[i]);    
    }
    for(i=1;i<=n;i++)
        scanf("%d",&b[i]);
    for(i=1;i<=m;i++)
    for(j=1;j<=n;j++)
        scanf("%d",&cost[i][j]);  //仓库与商店的边权 
    build_edge(1);  //建立边权为正的边，跑最小费用最大流 
    mcmf();//最小费用最大流(Min Cost Max Flow ）的缩写 
    printf("%d",mincost); 
    maxwater=0;
    mincost=0; 
    cnt=1;
    memset(head,0,sizeof(head));
    build_edge(-1);//建立边权为符的边 
    mcmf();
    printf("\n%d",-mincost);
}