Cogs 739. [网络流24题] 运输问题(费用流)

1. [网络流24题] 运输问题

   ★★ 输入文件：tran.in 输出文件：tran.out 简单对比

   时间限制：1 s 内存限制：128 MB

   «问题描述：

   

   «编程任务：

   对于给定的m 个仓库和n 个零售商店间运送货物的费用，计算最优运输方案和最差运

   输方案。

   «数据输入：

   

   «结果输出:

   程序运行结束时，将计算出的最少运输费用和最多运输费用输出到文件tran.out中。

   输入文件示例 输出文件示例

   tran.in

   2 3

   220 280

   170 120 210

   77 39 105

   150 186 122

   tran.out

   48500

   69140

   对于所有数据：1<=N,M<=100

/*
最大/最小费用流.
*/
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define MAXN 410
#define INF 1e9
using namespace std;
int n,m,S,T,cut=1,minans,maxans,a[MAXN],b[MAXN],vis[MAXN],c[MAXN][MAXN],dis[MAXN],fa[MAXN],head[MAXN];
queue<int>q;
struct data{int u,v,next,c,f;}e[MAXN*MAXN*6];
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*f;
}
void add(int u,int v,int c,int f)
{
    e[++cut].u=u;e[cut].v=v;e[cut].c=c;e[cut].f=f;e[cut].next=head[u];head[u]=cut;
    e[++cut].u=v;e[cut].v=u;e[cut].c=0;e[cut].f=-f;e[cut].next=head[v];head[v]=cut;
}
bool bfs(int t)
{
    for(int i=S;i<=T;i++) dis[i]=INF;dis[S]=0;
    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].v;
            if(dis[v]>dis[u]+e[i].f&&e[i].c)
            {
                dis[v]=dis[u]+e[i].f;fa[v]=i;
                if(vis[v]!=t) vis[v]=t,q.push(v);
            }
        }
    }
    return dis[T]!=INF;
}
void mincost()
{
    int t=1,tmp,x;
    while(bfs(t))
    {
        tmp=fa[T];
        while(tmp) x=min(x,e[tmp].c),tmp=fa[e[tmp].u];
        tmp=fa[T];
        while(tmp)
        {
            e[tmp].c-=x;
            e[tmp^1].c+=x;
            tmp=fa[e[tmp].u];
        }
        minans+=dis[T]*x;
    }
}
bool bfs2(int t)
{
    for(int i=S;i<=T;i++) dis[i]=-INF;dis[S]=0;
    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].v;
            if(dis[v]<dis[u]+e[i].f&&e[i].c)
            {
                dis[v]=dis[u]+e[i].f;fa[v]=i;
                if(vis[v]!=t) vis[v]=t,q.push(v);
            }
        }
    }
    return dis[T]!=-INF;
}
void maxcost()
{
    int t=1,tmp,x;
    while(bfs2(t))
    {
        tmp=fa[T];
        while(tmp) x=min(x,e[tmp].c),tmp=fa[e[tmp].u];
        tmp=fa[T];
        while(tmp)
        {
            e[tmp].c-=x;
            e[tmp^1].c+=x;
            tmp=fa[e[tmp].u];
        }
        maxans+=dis[T]*x;
    }
}
int main()
{
    int x;
    freopen("tran.in","r",stdin);
    freopen("tran.out","w",stdout);
    n=read(),m=read();S=0,T=n+m+1;
    for(int i=1;i<=n;i++) a[i]=read(),add(S,i,a[i],0);
    for(int i=1;i<=m;i++) b[i]=read(),add(i+n,T,b[i],0);
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
          c[i][j]=read(),add(i,j+n,INF,c[i][j]);
    mincost();
    memset(head,0,sizeof head);
    memset(e,0,sizeof e);
    for(int i=1;i<=n;i++) add(S,i,a[i],0);
    for(int i=1;i<=m;i++) add(i+n,T,b[i],0);
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
          add(i,j+n,INF,c[i][j]);
    maxcost();
    printf("%d %d",minans,maxans);
    return 0;
}