[洛谷P4015]运输问题

题目大意：有m个仓库和n个商店。第i个仓库有 $a_{i}$ 货物，第j个商店需要$b_{j}$个货物。从第i个仓库运送每单位货物到第j个商店的费用为$c_{i,j}$​​。求出最小费用和最大费用

题解：费用流，最大费用的时候把价钱和答案都取反

卡点：1.数组开小

C++ Code：

#include<cstdio>

#include<cctype>

#include<cstring>

#define maxn 250

using namespace std;

const int inf=0x3f3f3f3f;

int n,m;

int mp[maxn][maxn],a[maxn],b[maxn];

int d[maxn],pre[maxn];

int q[maxn],h,t;

int st=1,ed;

int head[maxn],cnt=2;

bool vis[maxn];

struct Edge{

    int to,nxt,w,cost;

}e[maxn*maxn<<1];

char ch;

void read(int &x){

    ch=getchar();

    while (!isdigit(ch))ch=getchar();

    for (x=ch^48,ch=getchar();isdigit(ch);ch=getchar())x=x*10+(ch^48);

}

inline int min(int a,int b){return a<b?a:b;}

void add(int a,int b,int c,int d){

    e[cnt]=(Edge){b,head[a],c,d};head[a]=cnt;

    e[cnt^1]=(Edge){a,head[b],0,-d};head[b]=cnt^1;

    cnt+=2;

}

void build(int op=1){

    for (int i=1;i<=m;i++)add(st,i+1,a[i],0);

    for (int i=1;i<=n;i++)add(m+i+1,ed,b[i],0);

    for (int i=1;i<=m;i++){

        for (int j=1;j<=n;j++)add(i+1,m+j+1,inf,mp[i][j]*op);

    }

}

bool spfa(){

    int x;

    memset(d,0x3f,sizeof d);

    d[q[h=t=1]=st]=0;

    while (h<=t){

        vis[x=q[h++]]=false;

        for (int i=head[x];i;i=e[i].nxt){

            int to=e[i].to;

            if (e[i].w&&d[to]>d[x]+e[i].cost){

                d[to]=d[x]+e[i].cost;

                pre[to]=i;

                if (!vis[to])vis[q[++t]=to]=true;

            }

        }

    }

    return d[ed]!=inf;

}

int update(){

    int ans,mf=inf;

    for (int i=pre[ed];i;i=pre[e[i^1].to])mf=min(mf,e[i].w);

    ans=mf*d[ed];

    for (int i=pre[ed];i;i=pre[e[i^1].to])e[i].w-=mf,e[i^1].w+=mf;

    return ans;

}

void MCMF(int op=1){

    int ans=0;

    while (1){

	    int x;

	    memset(d,0x3f,sizeof d);

	    d[q[h=t=1]=st]=0;

	    while (h<=t){

	        vis[x=q[h++]]=false;

	        for (int i=head[x];i;i=e[i].nxt){

	            int to=e[i].to;

	            if (e[i].w&&d[to]>d[x]+e[i].cost){

	                d[to]=d[x]+e[i].cost;

	                pre[to]=i;

	                if (!vis[to])vis[q[++t]=to]=true;

	            }

	        }

	    }

	    if (d[ed]!=inf){

		    int mf=inf;

		    for (int i=pre[ed];i;i=pre[e[i^1].to])mf=min(mf,e[i].w);

		    ans+=mf*d[ed];

		    for (int i=pre[ed];i;i=pre[e[i^1].to])e[i].w-=mf,e[i^1].w+=mf;

		}else break;

	}

    printf("%d\n",ans*op);

}

int main(){

    read(m),read(n);

    for (int i=1;i<=m;i++)read(a[i]);

    for (int i=1;i<=n;i++)read(b[i]);

    for (int i=1;i<=m;i++){

        for (int j=1;j<=n;j++)read(mp[i][j]);

    }

    ed=n+m+2;

    build();

    MCMF();

    memset(head,0,sizeof head);cnt=2;

    build(-1);

    MCMF(-1);

    return 0;

}