1 条题解
-
1
题意
给出一个 个点 条边的有向有边权图。你可以对任意一条边执行操作使得该边边权加一。有 个询问，每个询问给出一个 ，求在操作次数不超过 的情况下 到 最短路的最大值。
$n \le 50,~m \le n \times (n-1),~w_i \le 10^6,~q \le 10^5,~x \le 10^5$
分析
先按照最短路定义以及题目要求列出不等式：
$$\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} $$以 为例可以画出下面的线性规划矩阵：
$$\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} $$即：
$$\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} $$发现其形式非常类似于最小费用最大流：令 为边 流量，第一条不等式限制除 和 以外的其他所有结点入流量不超过出流量，且 号点出流量比入流量大 ， 号点入流量比出流量大 ；第二条不等式限制每条边流量均不超过上限 ；令 为边 的费用，则最终答案即为网络总费用加上 。
为方便处理，我们将对偶线性规划矩阵最后一行乘上 ，倒数第二行除以 ，网络流限制变为：源点 到汇点 的流量为 ，每条边的最大流量为 ，每条边的费用为 。令网络在流量为 时最小费用为 ，则答案即为 。
做最小费用最大流过程中维护每一个流量对应的费用即可，利用其凸性可以预处理并快速解决询问。总时间复杂度 。
代码
Code
/** * @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; }
Macesuted
QWQ
LV 8
SU
@ 2022-2-24 21:25:06
- 1
