NYOJ1367 物流配送

题目描述:

物流配送是物流活动中一种非单一的业务形式，它与物品流动、资金流动紧密结合。备货是配送的准备工作或基础工作，备货工作包括筹集货源、订货或购货、集货、进货及有关的质量检查、结算、交接等。配送的优势之一，就是可以集中用户的需求进行一定规模的备货。备货是决定配送成败的初期工作，如果备货成本太高，会大大降低配送的效益。配送中的储存有储备及暂存两种形态。配送储备是按一定时期的配送经营要求，形成的对配送的资源保证。这种类型的储备数量较大，储备结构也较完善，视货源及到货情况，可以有计划地确定周转储备及保险储备结构及数量。

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

样例输出:

提示:

来源:

河南省第十一届ACM大学生程序设计竞赛

思路：裸的最小费用最大流。 a_i 连 S， b_i连T，流量为权值，费用为0。其他边流量为inf，费用w_i 。测试模板

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn=;

 const int maxm=;

 const int inf=0x3f3f3f3f;

 struct Edge{

     ll to,next,cap,flow,cost;

 }edge[maxm];

 int head[maxn],tol;

 int pre[maxn],dis[maxn];

 bool vis[maxn];

 int N;

 void init(int n) {

     N=n;

     tol=;

     memset(head,-,sizeof(head));

 }

 void addedge(int u,int v,ll cap,ll cost) {

     edge[tol].to=v;

     edge[tol].cap=cap;

     edge[tol].cost=cost;

     edge[tol].flow=;

     edge[tol].next=head[u];

     head[u]=tol++;

     edge[tol].to=u;

     edge[tol].cap=;

     edge[tol].cost=-cost;

     edge[tol].flow=;

     edge[tol].next=head[v];

     head[v]=tol++;

 }

 bool spfa(int s,int t) {

     queue<int> q;

     for(int i=;i<N;i++) {

         dis[i]=inf;

         vis[i]=false;

         pre[i]=-;

     }

     dis[s]=;

     vis[s]=true;

     q.push(s);

     while(!q.empty()) {

         int u=q.front();

         q.pop();

         vis[u]=false;

         for(int i=head[u];i!=-;i=edge[i].next) {

             int v=edge[i].to;

             if(edge[i].cap>edge[i].flow&&dis[v]>dis[u]+edge[i].cost) {

                 dis[v]=dis[u]+edge[i].cost;

                 pre[v]=i;

                 if(!vis[v]) {

                     vis[v]=true;

                     q.push(v);

                 }

             }

         }

     }

     if(pre[t]==-) return false;

     return true;

 }

 int minCostMaxflow(int s,int t,ll &cost) {

     int flow=;

     cost=;

     while(spfa(s,t)) {

         int Min=inf;

         for(int i=pre[t];i!=-;i=pre[edge[i^].to]) {

             if(Min>edge[i].cap-edge[i].flow)

                 Min=edge[i].cap-edge[i].flow;

         }

         for(int i=pre[t];i!=-;i=pre[edge[i^].to]) {

             edge[i].flow+=Min;

             edge[i^].flow-=Min;

             cost+=edge[i].cost*Min;

         }

         flow+=Min;

     }

     return flow;

 }

 int n;

 int main() {

     while(~scanf("%d",&n)) {

         init(n+);

         int x;

         for(int i=;i<=n;i++) {

             scanf("%d",&x);

             addedge(,i,x,);

             addedge(i,,,);

         }

         for(int i=;i<=n;i++) {

             scanf("%d",&x);

             addedge(i,n+,x,);

             addedge(n+,i,,);

         }

         for(int i=;i<=n-;i++) {

             int u,v,cost;

             scanf("%d%d%d",&u,&v,&cost);

             addedge(u,v,inf,cost);

             addedge(v,u,inf,cost);

         }

         ll cost=;

         minCostMaxflow(,n+,cost);

         printf("%lld\n",cost);

     }

 }

巴特西