BZOJ 2324 - [ZJOI2011]营救皮卡丘

#网络流 #费用流 #有上下界网络流

Published on 2016-04-07

描述

皮卡丘被火箭队用邪恶的计谋抢走了！这三个坏家伙还给小智留下了赤果果的挑衅！为了皮卡丘，也为了正义，小智和他的朋友们义不容辞的踏上了营救皮卡丘的道路。

火箭队一共有 $N$ 个据点，据点之间存在 $M$ 条双向道路。据点分别从 $1$ 到 $N$ 标号。小智一行 $K$ 人从真新镇出发，营救被困在 $N$ 号据点的皮卡丘。为了方便起见，我们将真新镇视为 $0$ 号据点，一开始 $K$ 个人都在 $0$ 号点。

由于火箭队的重重布防，要想摧毁 $K$ 号据点，必须按照顺序先摧毁 $1$ 到 $K-1$ 号据点，并且，如果 $K-1$ 号据点没有被摧毁，由于防御的连锁性，小智一行任何一个人进入据点 $K$ ，都会被发现，并产生严重后果。因此，在 $K-1$ 号据点被摧毁之前，任何人是不能够经过K号据点的。

为了简化问题，我们忽略战斗环节，小智一行任何一个人经过 $K$ 号据点即认为 $K$ 号据点被摧毁。被摧毁的据点依然是可以被经过的。

$K$ 个人是可以分头行动的，只要有任何一个人在 $K-1$ 号据点被摧毁之后，经过 $K$ 号据点， $K$ 号据点就被摧毁了。显然的，只要 $N$ 号据点被摧毁，皮卡丘就得救了。

野外的道路是不安全的，因此小智一行希望在摧毁 $N$ 号据点救出皮卡丘的同时，使得 $K$ 个人所经过的道路的长度总和最少。

请你帮助小智设计一个最佳的营救方案吧！

样例输入

样例输出

分析

显然每个点必须走一次，拆点，问题变为有下界的最小费用流，对于这个问题，我不想进行展开。
但是这样是不行的，仅仅保证了每一个点只经过一次，却没有保证经过的顺序是对的。换句话说，对于每个人走的路径，我们有可能不能构造出一个合法方案，使得任意一个人走到 $u$ 之前， $1 \rightarrow u - 1$ 全被走过！
那怎样才能保证是对的呢？跑一次 floyd，我们规定中转点只能比起点和终点的编号小，那么可以发现任意一条路径的中间点标号不会超过起点和终点。同时在构图的时候，只能从编号小的点 $u$ 走到编号大的点 $v$ ，且走两点之间 floyd 最短路！把这种构图方案记作方法 $M$ 。

我们用归纳法证明正确性：
按照方法 $M$ 构造，如果 $0 \rightarrow u - 1$ 这些点可以按顺序走过，那么 $0\rightarrow u$ 也可以按顺序走过。
证明：由于 $u$ 被走过一次，据刚刚的构造，一定有一条路径 $v\rightarrow u(v \le u)$ ，那么由于 $u - 1$ 被走过且 $v\rightarrow u(v \le u)$ 不会走过比 $u - 1$ 大的点，那么直接从 $v$ 走到 $u$ 即可，仍然成功按顺序走过。
又至少有一合法方案，所以有边 $(0, 1)$ ，故 $0 \rightarrow 1$ 可以按顺序走过，原命题为真。

接着证明：合法最优方案必定是可以由方法 $M$ 构造出来。
证明：假设有一个方案不能由方法 $M$ 构造，且该方案合法最优。
如果该方案违反只能从编号小的点 $u$ 走到编号大的点 $v$ ，这显然是多此一举。
如果该方案违反中转点只能比起点和终点的编号小，那么中转点要由别人走过，所以不是最优方案。

所以直接用 $M$ 构图跑即可。

代码

//  Created by Sengxian on 4/7/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 2324 上下界费用流
#include <algorithm>
#include <iostream>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;

inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}
typedef long long ll;
struct edge {
    int to, cap, cost, rev;
    edge(int to, int cap, int cost, int rev): to(to), cap(cap), cost(cost), rev(rev) {}
};
const int maxn = 150 + 3, INF = 0x3f3f3f3f;
struct MCMFwithBound {
    static const int maxNode = maxn * 2 + 10;
    vector<edge> G[maxNode];
    bool inq[maxNode];
    ll dis[maxNode];
    int preve[maxNode], prevv[maxNode];
    void addEdge(int f, int t, int cap, int cost) {
        G[f].push_back(edge(t, cap, cost, G[t].size()));
        G[t].push_back(edge(f, 0, -cost, G[f].size() - 1));
    }
    ll minCostMaxFlow(int s, int t, int flow) {
        ll res = 0;
        while (flow > 0) {
            queue<int> q;
            memset(dis, INF, sizeof dis);
            memset(inq, 0, sizeof inq);
            dis[s] = 0, inq[s] = true;
            q.push(s);
            while (!q.empty()) {
                int cur = q.front(); q.pop();
                inq[cur] = false;
                for (int i = 0; i < (int)G[cur].size(); ++i) {
                    edge &e = G[cur][i];
                    if (e.cap && dis[cur] + e.cost < dis[e.to]) {
                        dis[e.to] = dis[cur] + e.cost;
                        preve[e.to] = i;
                        prevv[e.to] = cur;
                        if (!inq[e.to]) {inq[e.to] = true; q.push(e.to);}
                    }
                }
            }
            if (dis[t] == INF) return -1;
            int d = flow;
            for (int cur = t; cur != s; cur = prevv[cur])
                d = min(d, G[prevv[cur]][preve[cur]].cap);
            flow -= d;
            res += dis[t] * d;
            for (int cur = t; cur != s; cur = prevv[cur]) {
                edge &e = G[prevv[cur]][preve[cur]];
                e.cap -= d;
                G[e.to][e.rev].cap += d;
            }
        }
        return res;
    }
    int S, T, allFlow;
    void init(int s, int t) {
        S = t + 1, T = S + 1;
        allFlow = 0;
    }
    void addEdge(int f, int t, int cost, int b, int c) {
        if (b) {
            addEdge(f, T, b, cost);
            addEdge(S, t, b, 0);
            addEdge(f, t, c - b, cost);
            allFlow += b;
        }else addEdge(f, t, c, cost);
    }
    ll minCostFlow(int s, int t) {
        addEdge(t, s, INF, 0);
        return minCostMaxFlow(S, T, allFlow);
    }
}MCMF;

int G[maxn][maxn];

int main() {
    int n = ReadInt() + 1, m = ReadInt(), k = ReadInt();
    int s = 0, t = n * 2;
    MCMF.init(s, t);
    MCMF.addEdge(0, 1, 0, 1, k);
    memset(G, INF, sizeof G);
    for (int i = 1; i < n; ++i)
        MCMF.addEdge(i * 2, i * 2 + 1, 0, 1, INF),
        MCMF.addEdge(i * 2 + 1, t, 0, 0, INF),
        G[i][i] = 0;
    for (int i = 0; i < m; ++i) {
        int fr = ReadInt(), to = ReadInt();
        G[fr][to] = G[to][fr] = min(G[fr][to], ReadInt());
    }
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if ((k <= i || k <= j) && G[i][k] + G[k][j] < G[i][j])
                    G[i][j] = G[i][k] + G[k][j];
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            MCMF.addEdge(i * 2 + 1, j * 2, G[i][j], 0, INF);
    printf("%lld\n", MCMF.minCostFlow(s, t));
    return 0;
}

BZOJ 3696 - 化合物 BZOJ 1565 - [NOI2009]植物大战僵尸

Sengxian's Blog