Description

W公司有m个仓库和n 个零售商店。第i 个仓库有ai个单位的货物;第j个零售商店需要bj个单位的货物。
货物供需平衡，即sigma(ai)==sigma(bj)。
从第i个仓库运送每单位货物到第j个零售商店的费用为Cij。试设计一个将仓库中所有货物运送到零售商店的运输方案，
使总运输费用最少。

Input

第1行有2 个正整数m和n，分别表示仓库数和零售商店数。
接下来的一行中有m个正整数ai，1≤i≤m，表示第i个仓库有ai个单位的货物。
再接下来的一行中有n个正整数bj，1≤j≤n，表示第j个零售商店需要bj个单位的货物。
接下来的m行，每行有n个整数，表示从第i个仓库运送每单位货物到第j个零售商店的费用Cij。

Output

程序运行结束时，将计算出的最少运输费用和最多运输费用输出

Sample Input

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

Sample Output

48500
69140


提交链接：运输问题


这个题看完题意就是个很水的题


因为建立一个源点S，给货物连边（S，Xi，i点的货物总量，INF）

每个货物连到每个商店（Xi，Yj，INF，i->j的单位费用）

建立一个汇点T，从商店连到T（）


然后就是裸的最小费用最大流和最大费用最大流啦！

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

const int maxm=1050;
const int maxn=1050;
const int INF=0x3f3f3f3f;
int s,t,tot,n,m;
int a[maxm];
int b[maxn];
int mp[maxm][maxn];

struct Edge{
    int to,nxt,cap,flow,cost;
}edge[105000];
int Head[maxn],tol;
int pre[maxn],dis[maxn];
bool vis[maxn];

void addedge(int u,int v,int cap,int cost){
    edge[tol].to=v;
    edge[tol].cap=cap;
    edge[tol].cost=cost;
    edge[tol].flow=0;
    edge[tol].nxt=Head[u];
    Head[u]=tol++;
    edge[tol].to=u;
    edge[tol].cap=0;
    edge[tol].cost=-cost;
    edge[tol].flow=0;
    edge[tol].nxt=Head[v];
    Head[v]=tol++;
}

bool spfa(int s,int t){
    queue<int> q;
    for(int i=0;i<tot;i++){
        dis[i]=INF;vis[i]=false;pre[i]=-1;
    }
    dis[s]=0;vis[s]=true;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=false;
        for(int i=Head[u];i!=-1;i=edge[i].nxt){
            int v=edge[i].to;
            if (edge[i].cap>edge[i].flow&&dis[v]>dis[u]+edge[i].cost){
                dis[v]=dis[u]+edge[i].cost;
                pre[v]=i;
                if (!vis[v]){
                    vis[v]=true;
                    q.push(v);
                }
            }
        }
    }
    if (pre[t]==-1) return false;
    return true;
}

int minCostMaxflow(int s,int t,int &cost){
    int flow=0;
    cost=0;
    while(spfa(s,t)){
        int Min=INF;
        for(int i=pre[t];i!=-1;i=pre[edge[i^1].to])
            if (Min>edge[i].cap-edge[i].flow)
                Min=edge[i].cap-edge[i].flow;
        for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]){
            edge[i].flow+=Min;
            edge[i^1].flow-=Min;
            cost+=edge[i].cost*Min;
        }
        flow+=Min;
    }
    return flow;
}

int main(){
    //freopen("input.txt","r",stdin);
    while(scanf("%d%d",&m,&n)!=EOF){
        for(int i=1;i<=m;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++) scanf("%d",&b[i]);
        for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&mp[i][j]);
        s=0;
        t=n+m+1;
        tot=t+1;
        memset(Head,-1,sizeof(Head));
        tol=0;
        for(int i=1;i<=m;i++)
            addedge(s,i,a[i],0);
        for(int i=1;i<=n;i++)
            addedge(i+m,t,b[i],0);
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
                addedge(i,j+m,INF,mp[i][j]);
        int cost;
        int flow=minCostMaxflow(s,t,cost);
        printf("%d\n",cost);
        memset(Head,-1,sizeof(Head));
        tol=0;
        for(int i=1;i<=m;i++)
            addedge(s,i,a[i],0);
        for(int i=1;i<=n;i++)
            addedge(i+m,t,b[i],0);
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
                addedge(i,j+m,INF,-mp[i][j]);
        flow=minCostMaxflow(s,t,cost);
        printf("%d\n",-1*cost);
    }
    return 0;
}