B题
知识点:最大权闭合子图(网络流)+ 树链剖分、线段树优化建图
感觉只要学一下最大权闭合子图是啥,会线段树优化就能会做了...
只是代码又长又臭,写晕了。还有网络流dinic一定要当前弧优化,不然tle....
闭合子图:原图中选一个点集,点集中所有点和它们的出边构成新图,称为闭合子图。(选了一个点就必须选它的后继点)
最大权闭合子图求法:
源点和所有正权点连边,流量为这个正权;所有负权点和汇点连边,流量为负权的相反数;原图的边,和连边,流量为无穷大。
最大权闭合子图的权值 = 所有正权 - 最大流
个人理解:流量从源点出发,到正权代表的点,到负权代表的点,再到汇点,这个过程可以理解为选择了正权点,然后正权点的贡献被负权点抵消了。
为啥不会选择负权大于正权。因为流量都要通过正权流出,正权流出多少流量,负权就只能接受这么多流量(流量守恒),所以负权大于正权时,正负抵消,相当于不选这个正权点,也就不会选这个负权点。
因此在网络流中,最大权闭合子图=它自己正负权相减,变成了,所有正权和 -(最大权闭合子图的负权 + 会带来负贡献的正权)
在本题中,路线(只保留正收益)视为上面的正权点,树上的边视为上面的负权点,然后跑网络流就搞定了。
但是n和m都有1e4,直接建图高达1e8的边.....
可以树链剖分,然后一条路线实际上就是一个区间,再用线段树将这个区间划分成 log 个区间,将路线和这些区间连边即可。
(感觉会做CF786B,也能很轻松理解这个这题的线段树优化)
#include <bits/stdc++.h> using namespace std; using LL = long long; using PII = pair<int, int>; #define lson (k << 1) #define rson (k << 1 | 1) const int N = 3 + 1e4; int n, m; namespace Dinic { struct Edge { int ver, next, flow; } E[N * 200]; int head[N * 200], cur[N * 200], id = 1; int maxFlow; int d[N * 200]; int nodeId; // 用于记录当前网络流,图中有多少个点 const int s = ++nodeId; // 源 const int t = ++nodeId; // 汇 void addEdge(int u, int v, int f) { E[++id] = {v, head[u], f}; head[u] = id; E[++id] = {u, head[v], 0}; head[v] = id; } int bfs() { queue<int> q; q.push(s); for (int i = 1; i <= nodeId; ++i) { d[i] = 0; cur[i] = head[i]; } d[s] = 1; while (q.size()) { int x = q.front(); q.pop(); for (int i = cur[x]; i; i = E[i].next) { int y = E[i].ver; if (E[i].flow && !d[y]) { d[y] = d[x] + 1; q.push(y); } } } return d[t]; } int dfs(int x, int f) { if (x == t || f == 0) { return f; } int flow = 0; for (int &i = cur[x]; i && f > flow; i = E[i].next) { int y = E[i].ver; if (d[y] != d[x] + 1) { continue; } int t = dfs(y, min(f - flow, E[i].flow)); flow += t; E[i].flow -= t; E[i ^ 1].flow += t; if (f == flow) { return flow; } } return flow; } int run() { while (bfs()) { maxFlow += dfs(s, 1e9); } return maxFlow; } }; // namespace Dinic namespace Tree { struct E { int y, id; // 边(x,y),在网络流建图中点编号为id }; vector<E> edge[N]; int sz[N], top[N], fa[N], son[N], dfn[N], d[N], id; int p[N]; // 边(x,y),d[x]<d[y],id存到p[y] int w[N]; // w[i]含义,p[x]的dfs序为i,w[i]就是p[x] struct TreeNode { int l, r; int v; // [l,r]区间代表的点在网络流建图中的点的编号 } tr[N << 2]; void addEdge(int u, int v, int id) { edge[u].push_back({v, id}); edge[v].push_back({u, id}); } void dfs1(int x, int fa) { d[x] = d[fa] + 1; sz[x] = 1; Tree::fa[x] = fa; for (auto &[y, id] : edge[x]) { if (y == fa) { continue; } p[y] = id; dfs1(y, x); sz[x] += sz[y]; if (sz[y] > sz[son[x]]) { son[x] = y; } } } void dfs2(int x, int fa, int topf) { dfn[x] = ++id; top[x] = topf; w[id] = p[x]; if (son[x]) { dfs2(son[x], x, topf); } for (auto &[y, id] : edge[x]) { if (y == fa || y == son[x]) { continue; } dfs2(y, x, y); } } void segmentTreeBuild(int k, int l, int r, vector<int> ve) { tr[k].l = l; tr[k].r = r; tr[k].v = ++Dinic::nodeId; ve.push_back(tr[k].v); if (l == r) { if (r != 1) { // 1号点没有存边 for (auto x : ve) { // 将线段树区间包含r的区间,和r连边 Dinic::addEdge(x, w[r], 1e9); } } return; } int mid = l + r >> 1; segmentTreeBuild(lson, l, mid, ve); segmentTreeBuild(rson, mid + 1, r, ve); } void update(int k, int l, int r, int t) { if (l <= tr[k].l && tr[k].r <= r) { Dinic::addEdge(t, tr[k].v, 1e9); return; } int mid = tr[k].l + tr[k].r >> 1; if (l <= mid) { update(lson, l, r, t); } if (r > mid) { update(rson, l, r, t); } } void addDinicEdge(int u, int v, int f) { int t = ++Dinic::nodeId; Dinic::addEdge(Dinic::s, t, f); while (top[u] != top[v]) { if (d[top[u]] < d[top[v]]) { swap(u, v); } update(1, dfn[top[u]], dfn[u], t); u = fa[top[u]]; } if (d[u] > d[v]) { swap(u, v); } if (dfn[u] + 1 <= dfn[v]) { // u这个存在边不在范围内,不能写成update(1, dfn[u], dfn[v], t); update(1, dfn[u] + 1, dfn[v], t); } } } // namespace Tree int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i < n; ++i) { int u, v, w; cin >> u >> v >> w; Tree::addEdge(u, v, ++Dinic::nodeId); Dinic::addEdge(Dinic::nodeId, Dinic::t, w); } Tree::dfs1(1, 0); Tree::dfs2(1, 0, 1); Tree::segmentTreeBuild(1, 1, n, {}); int ans = 0; while (m--) { int s, t, a, b; cin >> s >> t >> a >> b; if (a - b > 0) { Tree::addDinicEdge(s, t, a - b); ans += a - b; } } ans -= Dinic::run(); cout << ans << endl; return 0; }