题意:有M个货物供应点,它提供k种货物,有N个商店,这N个商店分别要从货物点订购一定量的这k种物品,每个供应点对这k种货物的供应量不同,每个商店对k种物品的需求量也不同,每个货物供应点向每个商店送不同种货物的单个物品的花费不同,现在给出货物供应点、商店、k种货物、花费间的关系,现在让你针对商店给出的订单,让你决定如何使所有供应点完成订单任务的最小花费,若能完成任务,则输出最小花费,否则输出-1.
为我的英语拙计啊。。。到网上找了翻译才看懂。。太水了。
第一次写费用流,参考了别人的代码,写了点注释,算是费用流第一A。纪念一下。。
贴代码
#include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <cmath> #include <cstring> #include <queue> #include <set> #include <vector> #include <stack> #include <map> #include <iomanip> #define PI acos(-1.0) #define Max 105 #define inf 1<<28 #define LL(x) (x<<1) #define RR(x) (x<<1|1) using namespace std; int c[Max][Max]; //流量限制 int f[Max][Max];//最大流 int dis[Max]; int w[Max][Max];//费用 bool visit[Max]; int path[Max]; int S,T; int q[Max*100]; int spfa()//最短路 { int i,j; for(i=0; i<=T; i++) dis[i]=inf,path[i]=-1,visit[i]=0; dis[S]=0; visit[S]=1; int num=0,cnt=0; q[num++]=S; while(num>cnt) { int temp=q[cnt++]; visit[temp]=0; for(i=1; i<=T; i++) if(c[temp][i]>f[temp][i]&&dis[temp]+w[temp][i]<dis[i]) { path[i]=temp; dis[i]=dis[temp]+w[temp][i]; if(!visit[i]) { visit[i]=1; q[num++]=i; } } } if(path[T]==-1) return 0; return 1; } void getMaxflow()//找增广路并调整流量 { while(spfa()) { int maxFlow=inf; int pre=T; while(path[pre]!=-1) { maxFlow=min(maxFlow,c[path[pre]][pre]-f[path[pre]][pre]); pre=path[pre]; } pre=T; while(path[pre]!=-1)//调整流量 { f[path[pre]][pre]+=maxFlow; f[pre][path[pre]]=-f[path[pre]][pre]; pre=path[pre]; } } } int need[Max][Max],have[Max][Max]; int cost[Max][Max][Max]; int main() { int i,j,k,l,n,m,d; while(scanf("%d%d%d",&n,&m,&k),(n+m+k)) { for(i=1; i<=n; i++) //客人i for(j=1; j<=k; j++) //需要货物j的数量 scanf("%d",&need[i][j]); for(i=1; i<=m; i++) //仓库i for(j=1; j<=k; j++) //有货物j的数量 scanf("%d",&have[i][j]); for(i=1; i<=k; i++) //第i个商品 for(j=1; j<=n; j++) //送到j地点 for(d=1; d<=m; d++) //从d地点的 scanf("%d",&cost[i][d][j]);//的费用 S=0,T=n+m+1;//超级源点0,超级汇点n+m+1; //cout<<1<<endl; bool flag=0; int ans=0; for(i=1; i<=k; i++) { memset(c,0,sizeof(c)); memset(f,0,sizeof(f)); memset(w,0,sizeof(w)); for(j=1; j<=m; j++)//源点到每个仓库的容量为该仓库这种物品的存量 c[0][j]=have[j][i]; for(j=1; j<=n; j++)//每个客人到汇点的容量为该客人对物品的需求量 c[m+j][T]=need[j][i]; for(j=1; j<=m; j++) for(d=1; d<=n; d++) c[j][d+m]=have[j][i];//每个仓库到每个客人之间的容量为该仓库这种物品的存量 for(j=1; j<=m; j++) for(d=1; d<=n; d++) w[j][d+m]=cost[i][j][d],w[d+m][j]=-w[j][d+m];//花费,负花费用于回流 getMaxflow(); //cout<<1<<endl; for(j=1; j<=n; j++) if(c[j+m][T]!=f[j+m][T])//如果不能供货,则输出-1 { flag=1; break; } if(flag) break; for(j=1; j<=m; j++) for(d=1; d<=n; d++) ans+=f[j][d+m]*w[j][d+m];//总费用 // cout<<1<<endl; } if(flag) cout<<"-1"<<endl; else cout<<ans<<endl; } return 0; }