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

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

卡点：1.数组开小

 

C++ Code：

#include
     
      #include
      
       #include
       
        #define maxn 250using 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
        
         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;}