题意：
有m个仓库，，n个零售商店，两两之间有运送货物的单位费用；
对于给定的仓库的储存量和商店的需求量，计算最优运输方案和最差运输方案；
题解：
建图：
从源点s到每个仓库连容量为货物数的边；
从每个商店到汇点t连容量为货物数的边；
仓库与商店间两两连容量无限，费用为单位费用的边；
分别求出最小费用最大流和最大费用最大流就是答案；
不过，对于最大费用的处理上，有两种方法；
第一种是将边的费用全都置为相反数，求出最小费用，再取反就是答案；
第二种是跑最长路的spfa，这样每次都是费用最大的增广路，也可以得到最大费用最大流；
但是第二种有些需要注意，数组必须清成负无穷，因为可能会在过程中出现负权无法处理；
还有就是最后判断能否增广时，最好判断负无穷而不是大于0；
因为题中要求的是最大流，而有可能为了使流最大而必须让费用减小；
由于这题本身性质，判>0可以通过，但是在深海机器人问题里就不可以了；
事实上，判断>0求出的是最大费用而不是最大流；
代码：
相反数法：
#include<queue>#include<stdio.h>#include<string.h>#include<algorithm>#define N 300#define M 11000using namespace std;queue<int>q;int to[M],val[M],flow[M],next[M],head[N],tot;int dis[N],pre[N],s,t;bool inq[N];void add(int x,int y,int v,int fl){to[++tot]=y,val[tot]=v,flow[tot]=fl,next[tot]=head[x],head[x]=tot;to[++tot]=x,val[tot]=-v,flow[tot]=0,next[tot]=head[y],head[y]=tot;}bool spfa(){memset(dis,0x3f,sizeof(dis));dis[s]=0;q.push(s),inq[s]=1;int x,y,i;while(!q.empty()){x=q.front(),q.pop();inq[x]=0;for(i=head[x];i;i=next[i]){if(flow[i]>0&&dis[y=to[i]]>dis[x]+val[i]){dis[y]=dis[x]+val[i];pre[y]=i;if(!inq[y])q.push(y),inq[y]=1;}}}if(dis[t]==0x3f3f3f3f)return 0;elsereturn 1;}int mcmf(){int i,fl=0x3f3f3f3f,ret=0;for(i=t;i;i=to[pre[i]^1])fl=min(fl,flow[pre[i]]);for(i=t;i;i=to[pre[i]^1])flow[pre[i]]-=fl,flow[pre[i]^1]+=fl,ret+=fl*val[pre[i]];return ret;}void rebuild(){for(int i=2;i<=tot;i+=2){flow[i]=flow[i]+flow[i^1];flow[i^1]=0;swap(val[i],val[i^1]);}}int main(){int n,m,i,j,k,x,y,v,ans;scanf("%d%d",&n,&m);s=0,t=n+m+1;for(i=1,tot=1;i<=n;i++)scanf("%d",&v),add(0,i,0,v);for(i=1;i<=m;i++)scanf("%d",&v),add(i+n,t,0,v);for(i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&v),add(i,j+n,v,0x3f3f3f3f);ans=0;while(spfa()){ans+=mcmf();}printf("%d\n",ans);rebuild();ans=0;while(spfa()){ans+=mcmf();}printf("%d\n",-ans);return 0;}
最长路法：
#include<queue>#include<stdio.h>#include<string.h>#include<algorithm>#define N 120#define M 6010using namespace std;queue<int>q;int to[M],val[M],flow[M],next[M],head[N],tot;int dis[N],pre[N],s,t;bool inq[N];void add(int x,int y,int v,int fl){to[++tot]=y,val[tot]=v,flow[tot]=fl,next[tot]=head[x],head[x]=tot;to[++tot]=x,val[tot]=-v,flow[tot]=0,next[tot]=head[y],head[y]=tot;}bool spfa1(){memset(dis,0x3f,sizeof(dis));dis[s]=0;q.push(s),inq[s]=1;int x,y,i;while(!q.empty()){x=q.front(),q.pop();inq[x]=0;for(i=head[x];i;i=next[i]){if(flow[i]>0&&dis[y=to[i]]>dis[x]+val[i]){dis[y]=dis[x]+val[i];pre[y]=i;if(!inq[y])q.push(y),inq[y]=1;}}}if(dis[t]==0x3f3f3f3f)return 0;elsereturn 1;}bool spfa2(){memset(dis,-0x3f,sizeof(dis));<span style="white-space:pre"></span>// 第一点注意dis[s]=0;q.push(s);inq[s]=1;int x,y,i;while(!q.empty()){x=q.front(),q.pop();inq[x]=0;for(i=head[x];i;i=next[i]){if(flow[i]>0&&dis[y=to[i]]<dis[x]+val[i]){dis[y]=dis[x]+val[i];pre[y]=i;if(!inq[y])q.push(y),inq[y]=1;}}}return dis[t]>-10000;//第二点注意 }int mcmf(){int i,fl=0x3f3f3f3f,ret=0;for(i=t;i;i=to[pre[i]^1])fl=min(fl,flow[pre[i]]);for(i=t;i;i=to[pre[i]^1])flow[pre[i]]-=fl,flow[pre[i]^1]+=fl,ret+=fl*val[pre[i]];return ret;}void rebuild(){for(int i=2;i<=tot;i+=2){flow[i]=flow[i]+flow[i^1];flow[i^1]=0;}}int main(){int n,m,i,j,k,x,y,v,ans;scanf("%d%d",&n,&m);s=0,t=n+m+1;for(i=1,tot=1;i<=n;i++)scanf("%d",&v),add(0,i,0,v);for(i=1;i<=m;i++)scanf("%d",&v),add(i+n,t,0,v);for(i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&v),add(i,j+n,v,0x3f3f3f3f);ans=0;while(spfa1()){ans+=mcmf();}printf("%d\n",ans);rebuild();ans=0;while(spfa2()){ans+=mcmf();}printf("%d\n",ans);return 0;}
那么前世我的目光一定一刻都没从你身上离开过吧！
