题意
给出一个 $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)$。
代码
/**
* @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;
}
Comments | NOTHING