nyoj 1367 ZZNUOJ 2109 物流配送(最小费用最大流)

Description:

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

Dr. Kong 所在的研究团队准备为Hai-E集团开发一个物流配送管理系统。已知Hai-E集团已经在全国各地建立了n个货物仓库基地，任意两个基地的货物可以相互调配。现在需要根据用户订货要求，来重新调配每个基地的货物数量。为了节流开源，希望对整个物流配送体系实行统一的货物管理和调度，能够提供一个全面完善的物流仓储配送解决方案，以减少物流配送过程中成本、人力、时间。

Input:

第一行： 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)

Output:

输出配送后的最小费用。

已知： a1+a2+…+an >=b1+b2+…+bn

Sample Input:

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

Sample Output:

题目链接

题目很明显的最小费用最大流裸题，要求出最后重新调配每个基地货物数量之后的最小花费，建图时源点连接每个货物仓库基地，容量为a[i]花费为0（初始时每个货物仓库基地有a[i]个货物），每个货物仓库基地链接汇点，容量为b[i]花费为0（因为要求最小化费，显然最大流为 $\sum_{i = 1}^{n} b_{i}$ ），最后在可调配路线上建边跑最小费用最大流即可，此题数据会爆int。

AC代码:

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 1e3 + 5;

struct Link {
    long long V, Cap, Cost, Flow, Next;
};

int N;
int A[maxn], B[maxn];
int Head[maxn];
int Path[maxn];
int Dis[maxn];
bool Vis[maxn];
int Tot;
Link edges[maxn << 7];

void Init() {
    Tot = 0;
    memset(Head, -1, sizeof(Head));
}

void AddEdge(int U, int V, long long Cap, long long Cost) {
    edges[Tot] = Link {V, Cap, Cost, 0, Head[U]};
    Head[U] = Tot++;
    edges[Tot] = Link {U, 0, -Cost, 0, Head[V]};
    Head[V] = Tot++;
}

bool Spfa(int Start, int End) {
    memset(Dis, INF, sizeof(Dis));
    memset(Vis, false, sizeof(Vis));
    memset(Path, -1, sizeof(Path));
    Dis[Start] = 0;
    Vis[Start] = true;
    std::queue<int> Que;
    while (!Que.empty()) {
        Que.pop();
    }
    Que.push(Start);
    while (!Que.empty()) {
        int U = Que.front();
        Que.pop();
        Vis[U] = false;
        for (int i = Head[U]; i != -1; i = edges[i].Next) {
            int V = edges[i].V;
            if (edges[i].Cap > edges[i].Flow && Dis[V] > Dis[U] + edges[i].Cost) {
                Dis[V] = Dis[U] + edges[i].Cost;
                Path[V] = i;
                if (!Vis[V]) {
                    Vis[V] = true;
                    Que.push(V);
                }
            }
        }
    }
    return Path[End] != -1;
}

int MinCostMaxFlow(int Start, int End, long long &MinCost) {
    int MaxFlow = 0;
    MinCost = 0;
    while (Spfa(Start, End)) {
        int Min = INF;
        for (int i = Path[End]; i != -1; i = Path[edges[i ^ 1].V]) {
            if (edges[i].Cap - edges[i].Flow < Min) {
                Min = edges[i].Cap - edges[i].Flow;
            }
        }
        for (int i = Path[End]; i != -1; i = Path[edges[i ^ 1].V]) {
            edges[i].Flow += Min;
            edges[i ^ 1].Flow -= Min;
            MinCost += edges[i].Cost * Min;
        }
        MaxFlow += Min;
    }
    return MaxFlow;
}

int main(int argc, char *argv[]) {
    while (~scanf("%d", &N)) {
        Init();
        for (int i = 1; i <= N; ++i) {
            scanf("%d", &A[i]);
            AddEdge(0, i, A[i], 0);
        }
        for (int i = 1; i <= N; ++i) {
            scanf("%d", &B[i]);
            AddEdge(i, N + 1, B[i], 0);
        }
        for (int i = 1, U, V, C; i < N; ++i) {
            scanf("%d%d%d", &U, &V, &C);
            AddEdge(U, V, INF, C);
            AddEdge(V, U, INF, C);
        }
        long long MinCost;
        MinCostMaxFlow(0, N + 1, MinCost);
        printf("%lld\n", MinCost);
    }
    return 0;
}