CodeChef CHEFBOOK - Chefbook

#数学 #网络流 #费用流 #线性规划 #差分约束

Published on 2016-12-17

题目地址

描述

PDF 传送门

分析

这道题目，每一次修改都会影响到很多位置，我们没办法直接求解。考虑建立出约束关系（最大化的值中没有写常数项，只需要最后加上即可）：

然而题目要求 $P_u, Q_u$ 是整数，而且 $m$ 高达 ${10}^4$ ，没有办法使用单纯形算法。我们考虑将这个问题对偶（设 $x_{u, v}$ 为第一行约束对偶后的变量， $y_{u, v}$ 为第二行约束对偶后的变量）：

这个对偶比较抽象，自己画一下矩阵或许更好理解。我们发现， $x_{u, v}, y_{u, v}$ 都只出现在两个式子中，而且系数一个是 $1$ 一个是 $-1$ ，回想起 NOI 2008 志愿者招募这一题的方法，可以考虑用网络流建模。考虑第一个约束：

\sum_{v}{(x_{u, v} - y_{u, v})}\ge \mathrm{degOut}(u), \quad u \in V

添加辅助变量，使其变成流量守恒的式子：

\sum_{v}{(x_{u, v} - y_{u, v})} - \mathrm{degOut}(u) - a_{u} = 0, \quad u \in V

对于第二个限制，利用同样的方法，添加辅助变量 $b_i$ 即可得到：

\sum_{v}{(-x_{u, v} + y_{u, v})} + \mathrm{degIn}(u) - b_{u} = 0, \quad u \in V

在此基础上，最小化：

我们考虑如何建立费用流的图，先抽象的理解一下：将变量看作边，则费用就是它在答案中的系数。而对于约束，我们看作点，是利用这个点的流入流量等于流出流量来满足变量之间的约束。在一个约束 $u$ 中，如果变量 $x$ 的系数为 $1$ ，那么就表示流入的流量，反之为流出。因为流入和流出是必然同时发生的，所以能够建出图的前提条件是必然要满足 $x$ 在两个约束中一个是 $1$ 一个是 $-1$ 。而对于常数项，我们是在向源点或者汇点直接连边，因为源点和汇点不需要满足流量守恒。

具体来说，对于第一类约束 $u$ ，建立点 $u$ ；对于第二类约束 $v$ ，建立点 $v + n$ 。对于边 $(u, v)$ ，从 $v + n$ 向 $u$ 连一条容量为 $\infty$ ，费用为的边，同时从 $u$ 向 $v + n$ 连一条容量为 $\infty$ ，费用为的边。对于约束中的常数项，对于每个点 $u$ ，从源点 $S$ 向 $u + n$ 连一条费用为 $0$ ，容量为 $\mathrm{degIn}(u)$ 的边，从 $u$ 向汇点连一条费用为 $0$ ，容量为 $\mathrm{degOut}(u)$ 的边。至于辅助变量，从 $u + n$ 向 $T$ 连接一条费用为 $0$ ，容量为 $\infty$ 的边。

由于 $\mathrm{degOut}(u)$ 和 $\mathrm{degIn}(u)$ 的边都必须满流，所以我们要做有下界的最小费用流。

可是这未免太麻烦了吧，我们找一找有没有什么简洁一点的方法。我们发现，从源点出发的边的容量和与流向汇点的边的容量和是一样的，都是边数 $m$ ，这就意味着，没必要强制边满流，只需要做最小费用最大流即可，而且无需添加辅助变量（因为辅助变量的流量必然是 $0$ ）！

现在我们求出了答案，怎么输出方案呢？由于我们求出的对偶后的变量 $x, y$ 不是我们要求的 $P, Q$ ，所以我们考虑对偶后与对偶前变量之间的关系，由此求出对偶前的变量。在对偶后的最优解中，如果 $x_{u, v} > 0$ ，那么在对偶前的最优解中，满足（来自互松弛定理，这个约束同时也是满足最优解的充分条件）：

同理如果 $y_{u, v} > 0$ ，必然有：

还有来自原线性规划的约束：

这就是一个差分约束的模型了，对于等式拆为两个不等式，然后连边即可（如果熟悉差分约束系统的话，连边应该很简单，这里不写了）。值得注意的是，本题中限制 $P_u, Q_u$ 必须在 $[0, 10^6]$ 之内，如果求出了负数，可以在最后给所有的 $P_u, Q_u$ 都加一个大常数（显然不影响约束以及结果）。但是这样做有可能会爆上界（我就是因为这个，WA 无数次）！所以正确的做法是加入两条限制：

这样是不会导致无解的，因为 $T_{u, v} - S_{u, v} \le 2000$ ，答案不会跨过 $10^6$ 这么大。

代码

//  Created by Sengxian on 2016/12/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  CodeChef CHEFBOOK 线性规划 -> 网络流 + 差分约束
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int readInt() {
    static int n, ch;
    static bool flag;
    n = 0, ch = getchar(), flag = false;
    while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return flag ? -n : n;
}

const int MAX_N = 105 + 3, MAX_M = 10005 + 3, INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
int n, m, degIn[MAX_N], degOut[MAX_N];

namespace MinCostMaxFlow {
    const int MAX_NODE = MAX_N * 2 + 3;
    struct edge {
        int to, cost, cap, rev;
        edge(int to, int cost, int cap, int rev): to(to), cost(cost), cap(cap), rev(rev) {}
    };
    vector<edge> G[MAX_NODE];
    void init() {
        for (int i = 0; i < MAX_NODE; ++i) G[i].clear();
    }

    inline void addEdge(int f, int t, int cap, int cost) {
        G[f].push_back(edge(t, cost, cap, G[t].size()));
        G[t].push_back(edge(f, -cost, 0, G[f].size() - 1));
    }

    ll dis[MAX_NODE];
    int preve[MAX_NODE], prevv[MAX_NODE], cnt[MAX_NODE];
    bool inq[MAX_NODE];

    ll minCostMaxFlow(int s, int t, int flow) {
        ll ans = 0;
        while (flow) {
            queue<int> q;
            memset(dis, 0x3f, sizeof dis);
            memset(inq, 0, sizeof inq);
            memset(cnt, 0, sizeof cnt);

            q.push(s), dis[s] = 0;
            while (!q.empty()) {
                int u = q.front(); q.pop();
                inq[u] = false;
                if (cnt[u]++ >= t + 10 + 1) return -1; // negative circle
                for (int i = 0; i < (int)G[u].size(); ++i) {
                    edge &e = G[u][i];
                    if (e.cap && e.cost + dis[u] < dis[e.to]) {
                        dis[e.to] = dis[u] + e.cost;
                        prevv[e.to] = u, preve[e.to] = i;
                        if (!inq[e.to]) {
                            q.push(e.to), inq[e.to] = true;
                        }
                    }
                }
            }
            if (dis[t] == INFLL) return -1;

            int d = flow;
            for (int u = t; u != s; u = prevv[u]) d = min(d, G[prevv[u]][preve[u]].cap);
            ans += d * dis[t];
            flow -= d;
            for (int u = t; u != s; u = prevv[u]) {
                edge &e = G[prevv[u]][preve[u]];
                e.cap -= d;
                G[e.to][e.rev].cap += d;
            }
        }
        return ans;
    }
}

using namespace MinCostMaxFlow;

namespace SPFA {
    const int MAX_NODE = MAX_N * 2;
    struct edge {
        int to, cost;
        edge(int to = 0, int cost = 0): to(to), cost(cost) {}
    };
    vector<edge> G[MAX_NODE];
    void init() {
        for (int i = 0; i < MAX_NODE; ++i) G[i].clear();
    }

    inline void addEdge(int u, int v, int w) {
        G[u].push_back(edge(v, w));
    }

    ll dis[MAX_NODE];
    bool inq[MAX_NODE];

    inline void spfa(int s) {
        queue<int> q;
        memset(dis, 0x3f, sizeof dis);
        memset(inq, 0, sizeof inq);

        q.push(s), dis[s] = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            inq[u] = false;
            for (int i = 0; i < (int)G[u].size(); ++i) {
                edge &e = G[u][i];
                if (e.cost + dis[u] < dis[e.to]) {
                    dis[e.to] = dis[u] + e.cost;
                    if (!inq[e.to]) q.push(e.to), inq[e.to] = true;
                }
            }
        }
    }
}

void printAns() {
    for (int u = 0; u < 2 * n; ++u)
        for (int i = 0; i < (int)G[u].size(); ++i) {
            edge &e = G[u][i];
            if (G[e.to][e.rev].cap) SPFA::addEdge(e.to, u, -e.cost);
        }
    // 必须采用这种方式，保证答案小于 1000000
    for (int i = 0; i < n * 2; ++i) SPFA::addEdge(n * 2, i, 1000000);
    for (int i = 0; i < n * 2; ++i) SPFA::addEdge(i, n * 2, 0);
    SPFA::spfa(n * 2);
    for (int i = 0; i < n; ++i) printf("%lld%c", SPFA::dis[i], i + 1 == n ? '\n' : ' ');
    for (int i = 0; i < n; ++i) printf("%lld%c", SPFA::dis[n + i], i + 1 == n ? '\n' : ' ');
}

int main() {
    int caseNum = readInt();
    while (caseNum--) {
        init();
        n = readInt(), m = readInt();
        int S = n * 2, T = S + 1;
        ll ans = 0;
        memset(degIn, 0, sizeof degIn);
        memset(degOut, 0, sizeof degOut);
        SPFA::init();
        for (int i = 0; i < m; ++i) {
            int u = readInt() - 1, v = readInt() - 1, w = readInt(), s = readInt(), t = readInt();
            degIn[v]++, degOut[u]++, ans += w;
            addEdge(v + n, u, INF, t - w);
            addEdge(u, v + n, INF, w - s);
            SPFA::addEdge(v + n, u, t - w);
            SPFA::addEdge(u, v + n, w - s);
        }

        for (int i = 0; i < n; ++i) {
            addEdge(i, T, degOut[i], 0);
            addEdge(S, i + n, degIn[i], 0);
        }

        ll res = minCostMaxFlow(S, T, m);
        if (res == -1) {
            puts("Unlike");
            continue;
        } else ans += res;
        printf("%lld\n", ans);
        printAns();
    }
    return 0;
}

虚树学习笔记 BZOJ 2445 - 最大团

Sengxian's Blog

CodeChef CHEFBOOK - Chefbook

描述

分析

代码