[CF903G]Yet Another Maxflow Problem

[CF903G]Yet Another Maxflow Problem

題目大意：

有\(A\)類點和\(B\)類點各\(n(n\le2\times10^5)\)個，所有\(A_i\)到\(A_{i+1}\)有一條權值為\(a_i\)的有向邊，所有\(B_i\)到\(B_{i+1}\)有一條權值為\(b_i\)的有向邊，另有\(m(m\le2\times10^5)\)條從\(A_x\)到\(B_y\)的權值為有向邊。連續\(q(q\le2\times10^5)\)次操作將\(A_{v_i}\)與\(A_{v_i+1}\)之間的邊的權值改為\(w_i\)。問每次修改完畢后的從\(A_1\)到\(B_n\)的最大流。

思路：

根據最大流-最小割定理，題目所求相當于每次修改完畢后的最小割。定義\(A\)類點間的邊為\(A\)類邊，\(B\)類點間的邊為\(B\)類邊，\(AB\)類點間的邊為\(C\)類邊。假設兩類邊各\(n-1\)條之外還分別有一個邊權為\(0\)的邊，那么每次的最小割一定恰好包含一個\(A\)類邊、一個\(B\)類邊和若干\(C\)類邊。由于\(B\)類邊和\(C\)類邊都不會被修改，則對于同一個\(A\)類邊，對應的最優的\(B\)類邊是固定的。方便起見，下文將\(B_i\)到\(B_{i+1}\)的邊記作\(b_{i+1}\)，不同于題面描述。

考慮預處理每個\(A\)類邊對應的最優\(B\)類邊。不難發現，若我們選擇了\(a_i\)和\(b_j\)兩條邊，要使得\(A_1\)與\(B_n\)不連通，則我們還需要割去所有連接\(A_x,B_y(x\le i,y\ge j)\)的\(C\)類邊，而這也是選擇\(a_i\)和\(b_j\)后的最小割。反過來說，連接\(A_x,B_y\)的\(C\)類邊會對\(a_i,b_j(x\le i,y\ge j)\)的選擇產生影響。因此我們可以\(1\sim n\)枚舉每個\(a_i\)，用線段樹維護對應每個\(b_j\)所需要的最小割的大小。首先將所有\(b_j\)加入到線段樹中，對于當前枚舉到的\(a_i\)，枚舉從\(A_i\)出發的所有\(C\)類邊，若對應的點為\(B_j\)，權值為\(w\)，將區間\([1,j]\)加上\(w\)，表示對于\(a_i\)及\(a_i\)以后的\(A\)類邊，若還要考慮\(b_j\)及\(b_j\)以前的\(B\)類邊作為對應邊，一定要割去這條\(C\)類邊。而每次插入后線段樹最小元素就是對應當前\(a_i\)，由一個\(B\)類邊和若干\(C\)類邊組成的、能與\(a_i\)構成割的邊權和，記這一邊權和為\(sum\)，則選擇\(a_i\)時的最小割為\(sum+a_i\)，記作\(c_i\)。

考慮修改操作，由于\(a_i\)對應的\(B\)類邊和\(C\)類邊已經確定，每次修改時\(a_i\)的變化也就是\(c_i\)的變化。用一些數據結構維護所有\(c_i\)的最小值即可。時間復雜度\(\mathcal O((m+q)\log n)\)。

源代碼：

#include<cstdio>
#include<cctype>
#include<vector>
using int64=long long;
inline int getint() {register char ch;while(!isdigit(ch=getchar()));register int x=ch^'0';while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');return x;
}
constexpr int N=2e5+1;
int64 a[N],b[N],c[N];
using Edge=std::pair<int,int>;
std::vector<Edge> e[N];
class SegmentTree {#define _left <<1#define _right <<1|1private:int64 val[N<<2],tag[N<<2];void push_up(const int &p) {val[p]=std::min(val[p _left],val[p _right]);}void push_down(const int &p) {if(!tag[p]) return;val[p _left]+=tag[p];val[p _right]+=tag[p];tag[p _left]+=tag[p];tag[p _right]+=tag[p];tag[p]=0;}public:void build(const int &p,const int &b,const int &e,const int64 arr[]) {tag[p]=0;if(b==e) {val[p]=arr[b];return;}const int mid=(b+e)>>1;build(p _left,b,mid,arr);build(p _right,mid+1,e,arr);push_up(p);}void modify(const int &p,const int &b,const int &e,const int &l,const int &r,const int64 &v) {if(b==l&&e==r) {val[p]+=v;tag[p]+=v;return;}push_down(p);const int mid=(b+e)>>1;if(l<=mid) modify(p _left,b,mid,l,std::min(mid,r),v);if(r>mid) modify(p _right,mid+1,e,std::max(mid+1,l),r,v);push_up(p);}int64 query() const {return val[1];}#undef _left#undef _right
};
SegmentTree t;
int main() {const int n=getint(),m=getint(),q=getint();for(register int i=1;i<n;i++) {a[i]=getint(),b[i+1]=getint();}t.build(1,1,n,b);for(register int i=0;i<m;i++) {const int u=getint(),v=getint(),w=getint();e[u].push_back({v,w});}for(register int x=1;x<=n;x++) {for(register auto &j:e[x]) {const int &y=j.first,&w=j.second;t.modify(1,1,n,1,y,w);}c[x]=t.query()+a[x];}t.build(1,1,n,c);printf("%lld\n",t.query());for(register int i=0;i<q;i++) {const int x=getint(),v=getint();t.modify(1,1,n,x,x,v-a[x]);a[x]=v;printf("%lld\n",t.query());}return 0;
}