poj 2516 (费用流)
题意：有N个供应商，M个店主，K种物品。每个供应商对每种物品的的供应量已知，每个店主对每种物品的需求量的已知，从不同的供应商运送不同的货物到不同的店主手上需要不同的花费，又已知从供应商m送第k种货物的单位数量到店主n手上所需的单位花费。供应是否满足需求？如果满足，最小运费是多少？
思路：这题一读完就知道是费用流了，刚开始想着拆点，不过算了一下，把m个供应商拆成m*k个点，n个店主拆成n*k个点，加起来有5000多个点，肯定会超时的，看了网上说每种商品求一次费用流就可以了，就是100个点求50次。
#include<stdio.h>#include<queue>#include<string.h>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<int>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<sum)break;//如果i商品供不应求for(j=1;j<=n;j++){for(h=1;h<=m;h++)addedge(h,j+m,in[h][i],link[i][j][h]);}Mincost();if(mincost==-1)break;//第i种商品不能满足cost+=mincost;}if(i<=k)printf("-1\n");//有商品不能满足else printf("%d\n",cost);}return 0;}