题目链接
http://poj.org/problem?id=2516
题意
感觉网络流的题目意思都挺难理解的。
有N个商店，每个商店都有K种相同物品，现要从M个供应商进货，问能否满足所有商店的进货要求，如果满足输出最小费用，否则输出-1.
输入如下：
第一行是N M K.
一个N*K矩阵，a[i][j]表示第i号店进第j种物品的数量。
一个M*K矩阵，b[i][j]表示第i号仓库储备第j种物品的数量。
K个N*M矩阵，第k个矩阵中第i行第j列品k表示从第j个仓库进第k种物品到第i号店的费用。
分析
一开始的思路：每个店有k种物品，那么就拆成k个点；每个仓库有k种物品，那么也拆成k个点。对这N*K+M*K个点按要求连边跑费用流。而是否满足供应要求，只需看最大流是否满流即可。也就是看第一个N*K矩阵的矩阵和是否等于最大流。
敲完提交，发现运行错误，原来一开始邻接表的边数只给了1e4,而拆点后，需要(N*K )* (M*K)条边。调整了边数提交后，发现TLE。分析了下时间复杂度，想起SPFA费用流算法在稠密图上运行比较慢。
难道要换dijstra费用流？emmmmmmm，可以将一个稠密大图拆成多个小图，虽然小图依然是稠密图，但是减少的幅度是非常大的。从2500*2500到50*50.这样，只需建K次图，跑K遍SPFA费用流即可。
AC代码
//1141ms 0.4MB
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <iostream>
#define INF 0x3f3f3f3f
using namespace std;//建图所用
const int maxn=1e4+100;
const int maxe=1e4+1000;
const int maxv=1e4+100;
struct edge
{int to,w,next,c;//w是费用，c是残量网络的流量
}e[maxe<<1];
int head[maxv<<1],depth[maxv],cnt;
void init()
{memset(head,-1,sizeof(head));cnt=-1;
}
void add_edge(int u,int v,int w,int c)
{e[++cnt].to=v;e[cnt].w=w;e[cnt].c=c;e[cnt].next=head[u];head[u]=cnt;
}
void _add(int u,int v,int w,int c)
{add_edge(u,v,w,c);add_edge(v,u,-w,0);
}//费用流算法
int S,T;
int vis[maxn],dis[maxn],pre_v[maxn],pre_e[maxn];
bool spfa()//类似于EK算法，通过不停的找增广路,即找一条距离最小的路径
{memset(vis,0,sizeof(vis));queue<int> que;memset(dis,0x3f,sizeof(dis));//初始距离为无穷大dis[S]=0;que.push(S);vis[S]=1;while(!que.empty())//bfs{int u=que.front();que.pop();vis[u]=0;for(int i=head[u];i!=-1;i=e[i].next){int v=e[i].to;if(e[i].c>0 && dis[v]>dis[u]+e[i].w)//w表示费用，c表示残量网络的流量{dis[v]=dis[u]+e[i].w;//距离指标是费用pre_e[v]=i;//记录前驱边，即记录增广路pre_v[v]=u;//记录前驱点if(!vis[v])//bfs{vis[v]=1;que.push(v);}}}}if(dis[T]<INF) return true;return false;
}
int maxflow=0;
int augment()//调整残量网络并返回增广路的费用
{int flow=INF;//flow最终为当前增广路的流量int u=T;while(u!=S)//从汇点到源点逆着bfs中得到的路径走{flow=min(flow,e[pre_e[u]].c);//最大流是增广路流量的最小值u=pre_v[u];}u=T;while(u!=S){e[pre_e[u]].c-=flow;//将增广路上的流量都减去最大流e[pre_e[u]^1].c+=flow;u=pre_v[u];}maxflow+=flow;return flow*dis[T];//dis[T]表示T到汇点的距离，距离指标是费用
}
int cost()
{int ans=0;while(spfa())//不停的找增广路{ans+=augment();//累加增广路的费用}return ans;
}
int N,M,K;
int a[100][100],b[100][100];
int main()
{while(~scanf("%d%d%d",&N,&M,&K)){if(N==0 && M==0 && K==0) break;S=0,T=200;int ans=0,sum=0,tot=0;for(int i=1;i<=N;i++)//第i号店进第j种物品的数量for(int j=1;j<=K;j++){scanf("%d",&a[i][j]);sum+=a[i][j];}for(int i=1;i<=M;i++)//第i号仓库储备第j种物品的数量for(int j=1;j<=K;j++){scanf("%d",&b[i][j]);}for(int k=1;k<=K;k++)//将一个非常稠密大图分成k个较稀疏的小图以减少时间{init();maxflow=0;for(int i=1;i<=N;i++) _add(S,i,0,a[i][k]);for(int i=1;i<=M;i++) _add(i+N,T,0,b[i][k]);for(int i=1;i<=N;i++)for(int j=1;j<=M;j++){int x;scanf("%d",&x);_add(i,j+N,x,INF);}ans+=cost();//累加费用tot+=maxflow;//累加最大流}if(tot==sum)//满流，即每个供应都满足printf("%d\n",ans);elseprintf("-1\n");}return 0;
}