题目描述 Description

W 公司有m个仓库和n 个零售商店。第i 个仓库有ai 个单位的货物；第j 个零售商店

需要bj个单位的货物。货物供需平衡，即  sum(si）=sum(bj)

。从第i 个仓库运送每单位货物到

第j 个零售商店的费用为cij 。试设计一个将仓库中所有货物运送到零售商店的运输方案，

使总运输费用最少。

编程任务：

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

输入描述 Input Description

的第1行有2 个正整数m和n，分别表示仓库数和

零售商店数。接下来的一行中有m个正整数ai ，1≤i≤m，表示第i个仓库有ai 个单位的货

物。再接下来的一行中有n个正整数bj ，1≤j≤n，表示第j个零售商店需要bj 个单位的货

物。接下来的m行，每行有n个整数，表示从第i 个仓库运送每单位货物到第j个零售商店

的费用cij 。

输出描述 Output Description

将计算出的最少运输费用和最多运输费用输出

样例输入 Sample Input

2 3

220 280

170 120 210

77 39 105

150 186 122

样例输出 Sample Output

48500

69140

啊啊啊啊啊啊啊啊

又是上次的错误

调了一个多小时

感谢某位大佬（哭唧唧。。。）

题目本身其实并不难

只是要记得跑最短路时dis数组初始化为inf

跑

最长路时

dis数组初始化为-inf！dis数组初始化为-inf！dis数组初始化为-inf！

当没有负权边时可为-1，但是因为费用流反向弧费用为原流的相反数

所以原来为正数的边权变为了负数

所以

dis数组初始化为-inf！

每次都是因为仅初始为-1而调很久

所以保险起见都初始为-inf吧

代码写得略丑

见谅见谅

#include
       
        #include
        
         #include
         
          const int inf=0x3f3f3f3f,N=50000;struct node{	int to,next,v,c,from;}e[1000000],f[1000000];int first[N],dis[N],qu[N],bo[N],from[N],first2[N];int cnt=1,s,t,ans=0;void insert(int u,int v,int q,int c){	e[++cnt].to=v;e[cnt].from=u;e[cnt].next=first[u];first[u]=cnt;e[cnt].v=q;e[cnt].c=c;	e[++cnt].to=u;e[cnt].from=v;e[cnt].next=first[v];first[v]=cnt;e[cnt].v=0;e[cnt].c=-c;	cnt-=2;	f[++cnt].to=v;f[cnt].from=u;f[cnt].next=first2[u];first2[u]=cnt;f[cnt].v=q;f[cnt].c=c;	f[++cnt].to=u;f[cnt].from=v;f[cnt].next=first2[v];first2[v]=cnt;f[cnt].v=0;f[cnt].c=-c;}bool spfa(){	memset(dis,inf,4*(t+5));	int i=1,j=2;	qu[1]=s;bo[s]=1;dis[s]=0;	while(i!=j)	{		int r=qu[i++];bo[r]=0;if(i==N)	i=0;		for(int k=first[r];k;k=e[k].next)		{			if(e[k].v>0&&dis[e[k].to]>dis[r]+e[k].c)			{				dis[e[k].to]=dis[r]+e[k].c;				from[e[k].to]=k;				if(!bo[e[k].to])				{					if(dis[e[k].to]
          
           0&&dis[f[k].to]
           
            dis[i])						{						i--;if(i<0)	i=N-1;						qu[i]=f[k].to;					}					else qu[j++]=f[k].to;if(j==N)j=0;					bo[f[k].to]=1;				}			}			}	}	if(dis[t]==-inf)	return 0;	return 1;}void fa(){	int min=inf;	for(int k=from[t];k;k=from[e[k].from])	min=min