1367-物流配送
内存限制:128MB 时间限制:8000ms 特判: No
通过数:1 提交数:1 难度:4
题目描述:
物流配送是物流活动中一种非单一的业务形式，它与物品流动、资金流动紧密结合。备货是配送的准备工作或基础工作，备货工作包括筹集货源、订货或购货、集货、进货及有关的质量检查、结算、交接等。配送的优势之一，就是可以集中用户的需求进行一定规模的备货。备货是决定配送成败的初期工作，如果备货成本太高，会大大降低配送的效益。配送中的储存有储备及暂存两种形态。配送储备是按一定时期的配送经营要求，形成的对配送的资源保证。这种类型的储备数量较大，储备结构也较完善，视货源及到货情况，可以有计划地确定周转储备及保险储备结构及数量。
Dr. Kong 所在的研究团队准备为Hai-E集团开发一个物流配送管理系统。已知Hai-E集团已经在全国各地建立了n个货物仓库基地，任意两个基地的货物可以相互调配。现在需要根据用户订货要求，来重新调配每个基地的货物数量。为了节流开源，希望对整个物流配送体系实行统一的货物管理和调度，能够提供一个全面完善的物流仓储配送解决方案，以减少物流配送过程中成本、人力、时间。
输入描述:
第一行： n （1 ≤ n ≤ 1000） 第2行： a1 a2 …… an 表示n个基地当前的物品数量 (0≤ ai ≤ 106 ) 第3行： b1 b2 …… bn 表示调配后，每个基地i应不少于bi个物品 (0≤ bi ≤ 106) 接下来n-1行，每行三个整数： i j k 表示从第i基地调配一个物品到第j基地需要花费为k，或 从第j基地调配一个物品到第i基地需要花费为k。(0≤ k ≤ 10^6)
输出描述:
输出配送后的最小费用。 已知： a1+a2+…+an >=b1+b2+…+bn
样例输入:
复制
6
0 1 2 2 0 0
0 0 1 1 1 1
1 2 2
1 3 5
1 4 1
2 5 5
2 6 1
样例输出:
9
提示:
是个裸题把算是，当时没学不会，然后学了最大流之后，看了眼费用流的含义，对着题目yy着
建了个模，套了套模板竟然A了= =不知道是不是数据太水。
按照题目的意思一定存在一种方案使得满足所有条件，所以不必考虑不满流的情况。
建立一个源点S一个汇点T，S连向所有的点，容量是a[i]费用是0，表示每个地方可以免费获得
a[i]个物品，这与每个点初始有a[i]个物品是等价的。每个点向T连边，容量是b[i]费用是0，表示每个点
可以免费移到T b[i]个物品，(因为要求的是最小的费用，所以最大流显然设置为∑bi是最优的),然后跑
费用流就好了。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define inf 0x3f3f3f3f
#define pb push_back
#define pii pair<int,int>
struct Edge{
int v,cap,flow,cost,next;
}e[];
int first[],a[],b[],d[],f[],p[][],tot,N,S,T;
bool inq[];
void add(int u,int v,int cap,int flow,int cost){
e[tot]=Edge{v,cap,flow,cost,first[u]};
first[u]=tot++;
}
bool spfa(int &flow,int &cost){
memset(d,inf,sizeof(d));
memset(inq,,sizeof(inq));
d[S]=,inq[S]=,p[S][]=p[S][]=,f[S]=inf;
queue<int>q;
q.push(S);
while(!q.empty()){
int u=q.front();q.pop();
inq[u]=;
for(int i=first[u];~i;i=e[i].next){
if(e[i].cap>e[i].flow && d[e[i].v]>d[u]+e[i].cost){
d[e[i].v]=d[u]+e[i].cost;
p[e[i].v][]=i;
p[e[i].v][]=u;
f[e[i].v]=min(f[u],e[i].cap-e[i].flow);
if(!inq[e[i].v])q.push(e[i].v);
}
}
} if(d[T]==inf) return false;
flow+=f[T];
cost+=d[T]*f[T];
int u=T;
while(u!=S){
e[p[u][]].flow+=f[T];
e[p[u][]^].flow-=f[T];
u=p[u][];
}
return true;
}
void solve(){
int flow=,cost=;
while(spfa(flow,cost));
cout<<cost<<endl;
}
int main(){
while(scanf("%d",&N)==){
int u,v,w;
tot=,memset(first,-,sizeof(first));
S=N+,T=N+;
for(int i=;i<=N;++i){
scanf("%d",a+i);
add(S,i,a[i],,);
add(i,S,,,);
}
for(int i=;i<=N;++i){
scanf("%d",b+i);
add(i,T,b[i],,);
add(T,i,,,);
}
for(int i=;i<N;++i){
scanf("%d%d%d",&u,&v,&w);
add(u,v,inf,,w),add(v,u,,,-w);
add(v,u,inf,,w),add(u,v,,,-w);
}
solve();
}
return ;
}