CodeForces903G Yet Another Maxflow Problem 扫描线 + 线段树 + 最小割

以你之姓@ 2021-09-30 12:38 240阅读 0赞

给定两条链\\(A, B\\)，其中\\(A\\)链某些点向\\(B\\)链有连边，支持修改\\(A\\)链中的某条边权以及查询\\(A\_1\\)到\\(B\_n\\)的最大流

--------------------

显而易见，\\(A\\)和\\(B\\)链中一定满足左部分属于\\(S\\)集，右部分属于\\(T\\)集

枚举\\(A, B\\)的分界点在哪里，我们就能知道哪些边需要被割掉

可以发现，对于\\(A\\)链上的一个点而言，割\\(A,, B\\)之间的边以及\\(B\\)边的最小值是确定的

那么，对于\\(A\\)链上的每个点用扫描线预处理出这个最小值

然后最后再来一个线段树来维护\\(A\\)链上的权值即可

复杂度\\(O(n \\log n)\\)

--------------------

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define ll long long #define ri register int #define rep(io, st, ed) for(ri io = st; io <= ed; io ++) #define drep(io, ed, st) for(ri io = ed; io >= st; io --) #define gc getchar inline int read() { int p = 0, w = 1; char c = gc(); while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); } while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc(); return p * w; } const int sid = 2e5 + 5; int n, m, q; int X[sid], Y[sid]; struct myk { int a, b, v; friend bool operator < (myk x, myk y) { return x.a < y.a; } } Q[sid]; #define ls (o << 1) #define rs (o << 1 | 1) struct Kujuo_Miyako_Saiko { ll mi[sid << 2], add[sid << 2]; inline void build(int o, int l, int r) { if(l == r) { mi[o] = Y[l - 1]; return; } int mid = (l + r) >> 1; build(ls, l, mid); build(rs, mid + 1, r); mi[o] = min(mi[ls], mi[rs]); } inline void mdf(int o, int l, int r, int ml, int mr, ll v) { if(ml > r || mr < l) return; if(ml <= l && mr >= r) { mi[o] += v; add[o] += v; return; } int mid = (l + r) >> 1; mdf(ls, l, mid, ml, mr, v); mdf(rs, mid + 1, r, ml, mr, v); mi[o] = min(mi[ls], mi[rs]) + add[o]; } } km; ll V[sid]; inline void solve1() { km.build(1, 1, n); sort(Q + 1, Q + m + 1); for(ri i = 1, j = 1; i <= n; i ++) { while(Q[j].a == i && j <= m) km.mdf(1, 1, n, 1, Q[j].b, Q[j].v), j ++; V[i] = km.mi[1]; } } ll mi[sid << 2]; inline void build(int o, int l, int r) { if(l == r) { mi[o] = V[l] + X[l]; return; } int mid = (l + r) >> 1; build(ls, l, mid); build(rs, mid + 1, r); mi[o] = min(mi[ls], mi[rs]); } inline void mdf(int o, int l, int r, int p, int v) { if(l == r) { mi[o] = V[l] + v; return; } int mid = (l + r) >> 1; if(p <= mid) mdf(ls, l, mid, p, v); else mdf(rs, mid + 1, r, p, v); mi[o] = min(mi[ls], mi[rs]); } inline void solve2() { build(1, 1, n); printf("%lld\n", mi[1]); rep(i, 1, q) { int v = read(), w = read(); mdf(1, 1, n, v, w); printf("%lld\n", mi[1]); } } int main() { n = read(); m = read(); q = read(); rep(i, 1, n - 1) X[i] = read(), Y[i] = read(); rep(i, 1, m) Q[i].a = read(), Q[i].b = read(), Q[i].v = read(); solve1(); solve2(); return 0; }

转载于:https://www.cnblogs.com/reverymoon/p/10249139.html