题目描述
WW 公司有 mm 个仓库和 nn 个零售商店。第 ii 个仓库有 a_iai 个单位的货物；第 jj 个零售商店需要 b_jbj 个单位的货物。
货物供需平衡，即sumlimits_{i=1}^{m}a_i=sumlimits_{j=1}^{n}b_ji=1∑mai=j=1∑nbj 。
从第 ii 个仓库运送每单位货物到第 jj 个零售商店的费用为 c_{ij}cij 。
试设计一个将仓库中所有货物运送到零售商店的运输方案，使总运输费用最少。
输入输出格式
输入格式：
第 11 行有 22 个正整数 mm 和 nn ，分别表示仓库数和零售商店数。
接下来的一行中有 mm 个正整数 a_iai ，表示第 ii 个仓库有 a_iai 个单位的货物。
再接下来的一行中有 nn 个正整数 b_jbj ，表示第 jj 个零售商店需要 b_jbj 个单位的货物。
接下来的 mm 行，每行有 nn 个整数，表示从第 ii 个仓库运送每单位货物到第 jj 个零售商店的费用 c_{ij}cij 。
输出格式：
两行分别输出最小运输费用和最大运输费用。
输入输出样例
输入样例#1
代码语言：javascript复制2 3
220 280
170 120 210
77 39 105
150 186 122输出样例#1：
代码语言：javascript复制48500
69140说明
1 leq n, m leq 1001≤n,m≤100
挺裸的一道费用流
从S向仓库连容量为a，费用为0的边
从商店向T连容量为b，费用为0的边
从仓库向商店连容量为INF，费用为c的边
代码语言：javascript复制#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define AddEdge(x,y,z,f) add_edge(x,y,z,f),add_edge(y,x,-z,0)
using namespace std;
const int INF=1e8 10;
const int MAXN=1e4 10;
inline int read()
{
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10 c-'0';c=getchar();}
return x*f;
}
int N,M,S,T;
int ansflow,anscost;
int A[MAXN],B[MAXN],C[1001][1001];
struct node
{
int u,v,w,f,nxt;
}edge[MAXN];
int head[MAXN],num=2;
inline void add_edge(int x,int y,int z,int f)
{
edge[num].u=x;
edge[num].v=y;
edge[num].w=z;
edge[num].f=f;
edge[num].nxt=head[x];
head[x]=num ;
}
int dis[MAXN],vis[MAXN],Pre[MAXN];
int SPFA()
{
queue<int>q;
q.push(S);
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[S]=0;
while(q.size()!=0)
{
int p=q.front();q.pop();
vis[p]=0;
for(int i=head[p];i!=-1;i=edge[i].nxt)
{
if(edge[i].f>0&&dis[edge[i].v]>dis[p] edge[i].w)
{
dis[edge[i].v]=dis[p] edge[i].w;
Pre[edge[i].v]=i;
if(!vis[edge[i].v])
q.push(edge[i].v),vis[edge[i].v]=1;
}
}
}
return dis[T]<=INF;
}
int F()
{
int nowflow=INF;
for(int now=T;now!=S;now=edge[Pre[now]].u)
nowflow=min(nowflow,edge[Pre[now]].f);
for(int now=T;now!=S;now=edge[Pre[now]].u)
edge[Pre[now]].f-=nowflow,
edge[Pre[now]^1].f =nowflow;
anscost =nowflow*dis[T];
}
void MCMF()
{
while(SPFA()) F();
printf("%dn",abs(anscost));
anscost=0;
}
int main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#endif
memset(head,-1,sizeof(head));
N=read(),M=read();
S=N M 1;T=N M 2;
for(int i=1;i<=N;i )
A[i]=read();
for(int i=1;i<=M;i )
B[i]=read();
for(int i=1;i<=N;i )
for(int j=1;j<=M;j )
C[i][j]=read();
for(int i=1;i<=N;i )
AddEdge(S,i,0,A[i]);
for(int i=1;i<=M;i )
AddEdge(i N,T,0,B[i]);
for(int i=1;i<=N;i )
for(int j=1;j<=M;j )
AddEdge(i,j N,C[i][j],INF);
MCMF();
memset(head,-1,sizeof(head));
num=2;
for(int i=1;i<=N;i )
AddEdge(S,i,0,A[i]);
for(int i=1;i<=M;i )
AddEdge(i N,T,0,B[i]);
for(int i=1;i<=N;i )
for(int j=1;j<=M;j )
AddEdge(i,j N,-C[i][j],INF);
MCMF();
return 0;
}
