CF1307G Cow and Exercise

发布于 2022-02-24  430 次阅读


题目链接

题意

给出一个 $n$ 个点 $m$ 条边的有向有边权图。你可以对任意一条边执行操作使得该边边权加一。有 $q$ 个询问,每个询问给出一个 $x$,求在操作次数不超过 $x$ 的情况下 $1$ 到 $n$ 最短路的最大值。

$n \le 50,~m \le n \times (n-1),~w_i \le 10^6,~q \le 10^5,~x \le 10^5$

分析

先按照最短路定义以及题目要求列出不等式:

$$
\begin{aligned}
\text{maximize}~d_n - d_1 \\
\begin{cases}
d_j - d_i - a_{i,~j} \le w_{i,~j} \\
\sum a_{i,~j} \le x \\
d_i,~a_{i,~j} \ge 0
\end{cases}
\end{aligned}
$$

以 $n = 3$ 为例可以画出下面的线性规划矩阵:

$$
\begin{array}{ccccccccccc}
d_1 & d_2 & d_3 & a_{1,~2} & a_{1,~3} & a_{2,~1} & a_{2,~3} & a_{3,~1} & a_{3,~2} & & \\ \hline
-1 & +1 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & \le & w_{1,~2} \\
-1 & 0 & +1 & 0 & -1 & 0 & 0 & 0 & 0 & \le & w_{1,~3} \\
+1 & -1 & 0 & 0 & 0 & -1 & 0 & 0 & 0 & \le & w_{2,~1} \\
0 & -1 & +1 & 0 & 0 & 0 & -1 & 0 & 0 & \le & w_{2,~3} \\
+1 & 0 & -1 & 0 & 0 & 0 & 0 & -1 & 0 & \le & w_{3,~1} \\
0 & +1 & -1 & 0 & 0 & 0 & 0 & 0 & -1 & \le & w_{3,~2} \\
0 & 0 & 0 & +1 & +1 & +1 & +1 & +1 & +1 & \le & x \\
-1 & 0 & +1 & 0 & 0 & 0 & 0 & 0 & 0 & \ge & Ans \\
\end{array}
$$

我们纵向看该矩阵求出其对偶线性规划:

$$
\begin{array}{c|cccccccccc}
p_{1,~2} & -1 & +1 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & w_{1,~2} \\
p_{1,~3} & -1 & 0 & +1 & 0 & -1 & 0 & 0 & 0 & 0 & w_{1,~3} \\
p_{2,~1} & +1 & -1 & 0 & 0 & 0 & -1 & 0 & 0 & 0 & w_{2,~1} \\
p_{2,~3} & 0 & -1 & +1 & 0 & 0 & 0 & -1 & 0 & 0 & w_{2,~3} \\
p_{3,~1} & +1 & 0 & -1 & 0 & 0 & 0 & 0 & -1 & 0 & w_{3,~1} \\
p_{3,~2} & 0 & +1 & -1 & 0 & 0 & 0 & 0 & 0 & -1 & w_{3,~2} \\
q & 0 & 0 & 0 & +1 & +1 & +1 & +1 & +1 & +1 & x \\
& \ge & \ge & \ge & \ge & \ge & \ge & \ge & \ge & \ge & \le \\
& -1 & 0 & +1 & 0 & 0 & 0 & 0 & 0 & 0 & Ans \\
\end{array}
$$

即:

$$
\begin{aligned}
\text{minimize}~ \bigg( \sum w_{i,~j} \times p_{i,~j} \bigg) + x \times q \\
\begin{cases}
\sum_j p_{j,~i} - \sum_j p_{i,~j} \ge \begin{cases}
-1,& i=1 \\
0,& 1 < i < n \\
+1,& i=n \\
\end{cases}\\
-p_{i,~j} + q \ge 0 \\
p_{i,~j},~q \ge 0
\end{cases}
\end{aligned}
$$

发现其形式非常类似于最小费用最大流:令 $p_{i,~j}$ 为边 $i \to j$ 流量,第一条不等式限制除 $1$ 和 $n$ 以外的其他所有结点入流量不超过出流量,且 $1$ 号点出流量比入流量大 $1$,$n$ 号点入流量比出流量大 $1$;第二条不等式限制每条边流量均不超过上限 $q$;令 $w_{i,~j}$ 为边 $i \to j$ 的费用,则最终答案即为网络总费用加上 $x \times q$。

为方便处理,我们将对偶线性规划矩阵最后一行乘上 $flow$,倒数第二行除以 $q$,网络流限制变为:源点 $1$ 到汇点 $n$ 的流量为 $flow$,每条边的最大流量为 $1$,每条边的费用为 $w_{i,~j}$。令网络在流量为 $flow$ 时最小费用为 $cost$,则答案即为 $\dfrac {cost + x} {flow}$。

做最小费用最大流过程中维护每一个流量对应的费用即可,利用其凸性可以预处理并快速解决询问。总时间复杂度 $O(n \times m^2 + q \times \log m)$。

代码

View On GitHub

/**
 * @file 1307G.cpp
 * @author Macesuted (i@macesuted.moe)
 * @date 2022-02-24
 *
 * @copyright Copyright (c) 2022
 * @brief
 *      My Tutorial: https://macesuted.moe/article/cf1307g
 *
 */

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

#define MP make_pair
#define MT make_tuple

namespace io {
#define SIZE (1 << 20)
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
int f, qr;
inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); }
inline char getch(void) {
    return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++);
}
void putch(char x) {
    *oS++ = x;
    if (oS == oT) flush();
    return;
}
string getstr(void) {
    string s = "";
    char c = getch();
    while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch();
    while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) s.push_back(c), c = getch();
    return s;
}
void putstr(string str, int begin = 0, int end = -1) {
    if (end == -1) end = str.size();
    for (int i = begin; i < end; i++) putch(str[i]);
    return;
}
template <typename T>
T read() {
    T x = 0;
    for (f = 1, c = getch(); c < '0' || c > '9'; c = getch())
        if (c == '-') f = -1;
    for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15);
    return x * f;
}
template <typename T>
void write(const T& t) {
    T x = t;
    if (!x) putch('0');
    if (x < 0) putch('-'), x = -x;
    while (x) qu[++qr] = x % 10 + '0', x /= 10;
    while (qr) putch(qu[qr--]);
    return;
}
struct Flusher_ {
    ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io::getch;
using io::getstr;
using io::putch;
using io::putstr;
using io::read;
using io::write;

bool mem1;

#define maxn 55
#define maxm 2505

typedef pair<long long, int> pli;

class Dinic {
   private:
    struct Edge {
        int to, cap, cost, rev;
    };

    vector<vector<Edge>> graph;
    vector<long long> dist;
    vector<int> pre;
    vector<bool> vis;
    queue<int> que;
    int n;

   public:
    void resize(int _n) { return n = _n, graph.resize(n + 1), vis.resize(n + 1), dist.resize(n + 1), pre.resize(n + 1); }
    void addEdge(int from, int to, int cap, int cost) {
        return graph[from].push_back(Edge{to, cap, cost, (int)graph[to].size()}),
               graph[to].push_back(Edge{from, 0, -cost, (int)graph[from].size() - 1});
    }
    long long maxFlow(int S, int T) {
        for (int i = 1; i <= n; i++) dist[i] = numeric_limits<int>::max(), vis[i] = false;
        que.push(S), dist[S] = 0;
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            vis[p] = false;
            for (auto i : graph[p])
                if (i.cap && dist[i.to] > dist[p] + i.cost) {
                    dist[i.to] = dist[p] + i.cost, pre[i.to] = i.rev;
                    if (!vis[i.to]) vis[i.to] = true, que.push(i.to);
                }
        }
        if (dist[T] == numeric_limits<int>::max()) return 0;
        int p = T;
        while (p != S) {
            int x = graph[p][pre[p]].to;
            graph[x][graph[p][pre[p]].rev].cap--, graph[p][pre[p]].cap++;
            p = x;
        }
        return dist[T];
    }
} net;

long long cost[maxm], lim[maxm];

void solve(void) {
    int n = read<int>(), m = read<int>();
    net.resize(n);
    for (int i = 1, x, y, c; i <= m; i++) {
        x = read<int>(), y = read<int>(), c = read<int>();
        net.addEdge(x, y, 1, c);
    }
    int flow = 0;
    long long ret = net.maxFlow(1, n);
    while (ret) cost[flow + 1] = cost[flow] + ret, flow++, ret = net.maxFlow(1, n);
    for (int i = 1; i < flow; i++) lim[i] = cost[i + 1] * i - cost[i] * (i + 1);
    cout << setprecision(8);
    int q = read<int>();
    while (q--) {
        int x = read<int>(), p = lower_bound(lim + 1, lim + flow, x) - lim;
        cout << 1. * (cost[p] + x) / p << endl;
    }
    return;
}

bool mem2;

int main() {
#ifdef MACESUTED
    cerr << "Memory: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
#endif

    int _ = 1;
    while (_--) solve();

#ifdef MACESUTED
    cerr << "Time: " << clock() * 1000. / CLOCKS_PER_SEC << "ms" << endl;
#endif
    return 0;
}

我缓慢吐出一串啊吧啊吧并不再想说话