Problem Description
给你一个 \(n\) 个节点的树状铁路网络,维护一条边每天需要花费 \(c_i\) 代价。
现在有 \(m\) 条从 \(a_i\) 到 \(b_i\) ,每天的盈利为 \(x_i\) ,维护花费为 \(y_i\) 的路线可以运营。
你可以选择一部分路线运营,求每日的最大收益。
Input
第一行输入两个整数 \(n,m(2 \le n \le 10^4,1 \le m \le 10^4)\) 。
接下来 \(n-1\) 行每行输入三个整数 \(u_i,v_i,c_i(1 \le u_i,v_i \le n,1 \le c_i \le 10^5)\) ,表示 \(u_i,v_i\) 之间有一条维护花费为 \(c_i\) 的铁路 。
接下来 \(m\) 每行输入三个整数 \(a_i,b_i,x_i,y_i(1 \le a_i,b_i \le n,a_i \not= b_i,1 \le x_i,y_i \le 10^5)\) ,表示一条可运营的路线。
Output
输出每日的最大收益。
Solution
由于选择了一条线路之后,该线路内的所有边都需要维护,我们将路线视为一个权值为 \(x_i-y_i\) 的点 \(u_i\) , 边视为一个权值为 \(-c_i\) 的点 \(v_i\) ,可以很显然地发现这是一个最大权闭合子图的问题。
如此一来我们可以得到一个比较暴力的建图方式,那就是将源点 \(S\) 向每个 \(x_i-y_i > 0\) 的路线视为的点 \(u_i\) 连流量为 \(x_i-y_i\) 的边, 所有边视为的点 \(v_i\) 向汇点 \(T\) 连流量为 \(c_i\) 的边, \(u_i\) 向对应路径上的所有 \(v_i\) 连流量为 \(inf\) 的边,最后答案为 \(\sum\limits_{x_i-y_i>0}(x_i-y_i)-MaxFlow\)。
对于如何将边转成点,对于一条边我们可以将其深度较深的节点视为对应边的节点,这样一来每条边是有一一对应的节点的。而对于如何从路径对应的节点向边对应的节点连边,我们只需从 \(u_i\) 向除 \(lca(a_i,b_i)\) 以外的点 \(v_i\) 连边即可。
直接这样做流网络中的边数上界会达至 \(O(nm)\) 的级别,是无法通过此题的。但我们很显然地发现对于部分的 \(v_i\) 所构成的点集我们是可以重复利用的,又观察到该铁路网络是一棵树,那么我们便可以考虑采用树链剖分 \(+\) 线段树去优化建图。
我们先考虑对于一条路径在树剖后会被划分成 \(logn\) 条路径,再考虑对于线段树上一段 \(dfn\) 连续的路径会被划分成 \(logn\) 段,那么我们最终的边数就会变成 \(O(mlog^2n)\) 级别,而因为这个图是我们自己建的,数据其实并不能很好的卡掉,故配合上网络流的玄学复杂度我们可以跑过此题。
Code
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
constexpr int N = 1e5 + 10, M = 4e6 + 10, inf = 2e9;
struct Dinic {
int n, S, T;
int maxflow;
int dep[N], cur[N];
int head[N], e[M], flow[M], ne[M], idx;
inline void init(int _n, int _S, int _T) {
n = _n, S = _S, T = _T;
idx = 0;
for (int i = 0; i <= n; i++)head[i] = -1;
}
inline void addedge(int a, int b, int c) {
e[idx] = b, flow[idx] = c, ne[idx] = head[a], head[a] = idx++;
e[idx] = a, flow[idx] = 0, ne[idx] = head[b], head[b] = idx++;
}
bool bfs() {
queue<int>q;
memset(dep, -1, sizeof(int) * (n + 5));
dep[S] = 0, q.push(S);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = head[u]; i != -1; i = ne[i]) {
int v = e[i];
if (dep[v] == -1 && flow[i]) {
dep[v] = dep[u] + 1;
if (v == T)return true;
q.push(v);
}
}
}
return false;
}
int dfs(int u, int limit) {
if (u == T)return limit;
int ret = 0;
for (int i = cur[u]; i != -1 && ret < limit; cur[u] = i, i = ne[i]) {
int v = e[i];
if (dep[v] == dep[u] + 1 && flow[i]) {
int d = dfs(v, min(limit - ret, flow[i]));
if (d)ret += d, flow[i] -= d, flow[i ^ 1] += d;
else dep[v] = -1;
}
}
return ret;
}
int MaxFlow() {
maxflow = 0;
while (bfs()) {
memcpy(cur, head, sizeof(int) * (n + 5));
maxflow += dfs(S, inf);
}
return maxflow;
}
};
struct Heavy_Light_Decomposition {
int n;
int dfn[N], seq[N], totdfn;
int dep[N], siz[N], top[N], fa[N], wson[N];
int head[N], e[M], w[M], ne[M], idx;
inline void init(int _n) {
totdfn = idx = 0, n = _n;
for (int i = 0; i <= n; i++)head[i] = -1, wson[i] = 0;
}
inline void addedge(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = head[a], head[a] = idx++;
}
void dfs1(int u, int father) {
dep[u] = dep[father] + 1, fa[u] = father, siz[u] = 1;
for (int i = head[u]; i != -1; i = ne[i]) {
int v = e[i];
if (v == father)continue;
dfs1(v, u);
siz[u] += siz[v];
if (siz[v] > siz[wson[u]])wson[u] = v;
}
}
void dfs2(int u, int chead) {
dfn[u] = ++totdfn, top[u] = chead, seq[totdfn] = u;
if (wson[u])dfs2(wson[u], chead);
for (int i = head[u]; i != -1; i = ne[i]) {
int v = e[i];
if (v == fa[u] || v == wson[u])continue;
dfs2(v, v);
}
}
void work(int root) {
dfs1(root, 0);
dfs2(root, root);
}
};
int n, m;
Dinic F;
Heavy_Light_Decomposition H;
void build(int u, int l, int r) {
if (l == r) {
F.addedge(u + n, H.seq[r], inf);
return;
}
F.addedge(u + n, (u << 1) + n, inf);
F.addedge(u + n, (u << 1 | 1) + n, inf);
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
}
void SegAddedge(int u, int l, int r, int L, int R, int x) {
if (L > r || R < l)return;
if (L <= l && r <= R) {
F.addedge(x, u + n, inf);
return;
}
int mid = l + r >> 1;
SegAddedge(u << 1, l, mid, L, R, x);
SegAddedge(u << 1 | 1, mid + 1, r, L, R, x);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
F.init(5 * n + m + 10, 5 * n + m + 5, 5 * n + m + 6);
H.init(n + 5);
for (int i = 1; i <= n - 1; i++) {
int u, v, c;
cin >> u >> v >> c;
H.addedge(u, v, c), H.addedge(v, u, c);
}
H.work(1);
build(1, 1, n);
for (int u = 1; u <= n; u++) {
for (int i = H.head[u]; i != -1; i = H.ne[i]) {
if (H.e[i] == H.fa[u])F.addedge(u, F.T, H.w[i]);
//将边权等效转换为该边较深的节点且从负权点向汇点连边
}
}
int ans = 0;
for (int i = 1; i <= m; i++) {
int u, v, x, y;
cin >> u >> v >> x >> y;
if (x <= y)continue;
ans += x - y;
F.addedge(F.S, i + 5 * n, x - y);//从源点向正权点连边
while (H.top[u] != H.top[v]) {
if (H.dep[H.top[u]] < H.dep[H.top[v]])swap(u, v);
SegAddedge(1, 1, n, H.dfn[H.top[u]], H.dfn[u], i + 5 * n);
u = H.fa[H.top[u]];
}
if (H.dep[u] < H.dep[v])swap(u, v);
SegAddedge(1, 1, n, H.dfn[v] + 1, H.dfn[u], i + 5 * n);
// 注意此处需要dfn[v]需要加1,因为流网络中点存的是路径上的边集,如果没有加1,就意味着取了lca(u,v)到其父亲的边,与定义不符。
}
cout << ans - F.MaxFlow() << endl;
}
标签:dep,le,return,10,int,多校,wson,牛客,Link
From: https://www.cnblogs.com/w1ck/p/18061966