题意：有N个供应商，M个店主，K种物品。每个供应商对每种物品的的供应量已知，每个店主对每种物品的需求量的已知，从不同的供应商运送不同的货物到不同的店主手上需要不同的花费，又已知从供应商m送第k种货物的单位数量到店主n手上所需的单位花费。供应是否满足需求？如果满足，最小运费是多少？
思路：这题一读完就知道是费用流了，刚开始想着拆点，不过算了一下，把m个供应商拆成m*k个点，n个店主拆成n*k个点，加起来有5000多个点，肯定会超时的，看了网上说每种商品求一次费用流就可以了，就是100个点求50次。
#include#include #include const int inf=0x3fffffff;const int N=200;using namespace std;int dis[N],start,end,head[N],num,sum,pre[N],vis[N],mincost;int in[51][51],out[51][51],link[51][51][51];struct edge{ int st,ed,flow,cost,next;}e[N*N];void addedge(int x,int y,int f,int c){ e[num].st=x;e[num].ed=y;e[num].flow=f;e[num].cost=c; e[num].next=head[x];head[x]=num++; e[num].st=y;e[num].ed=x;e[num].flow=0;e[num].cost=-c;e[num].next=head[y];head[y]=num++;}bool spfa(){ queue Q; int i,u,v; for(i=start;i<=end;i++) { pre[i]=-1; dis[i]=inf; vis[i]=0; } dis[start]=0; vis[start]=1; Q.push(start); while(!Q.empty()) { u=Q.front(); Q.pop(); vis[u]=0; for(i=head[u];i!=-1;i=e[i].next) { v=e[i].ed; if(e[i].flow<=0)continue; if(dis[v]>dis[u]+e[i].cost) { dis[v]=dis[u]+e[i].cost; pre[v]=i; if(!vis[v]) { Q.push(v); vis[v]=1; } } } } if(pre[end]==-1) return false; return true;}void Mincost(){ int i,minflow,maxflow=0; mincost=0; while(spfa()) { minflow=inf; for(i=pre[end];i!=-1;i=pre[e[i].st]) if(minflow>e[i].flow) minflow=e[i].flow; for(i=pre[end];i!=-1;i=pre[e[i].st]) { e[i].flow-=minflow; e[i^1].flow+=minflow; mincost+=minflow*e[i].cost; } maxflow+=minflow; } if(maxflow!=sum) mincost=-1;}int main(){ int i,j,n,k,m,h,sum1,cost; while(scanf("%d%d%d",&n,&m,&k),n+m+k) { start=0,end=n+m+1;cost=0; for(i=1;i<=n;i++) for(j=1;j<=k;j++) scanf("%d",&out[i][j]); for(i=1;i<=m;i++) { for(j=1;j<=k;j++) scanf("%d",&in[i][j]); } for(i=1;i<=k;i++) { for(j=1;j<=n;j++) for(h=1;h<=m;h++) scanf("%d",&link[i][j][h]); } for(i=1;i<=k;i++)//第i种商品 { memset(head,-1,sizeof(head)); num=0;sum=0;sum1=0; for(j=1;j<=n;j++)//商店需要的i种商品 { sum+=out[j][i]; addedge(m+j,end,out[j][i],0); } for(j=1;j<=m;j++) { addedge(start,j,in[j][i],0); sum1+=in[j][i]; } if(sum1