题目
题目链接:https://codeforces.com/problemset/problem/903/G
一张图分为两部分,左右都有 (n) 个节点,(A_i
ightarrow A_{i+1}) 连边,(B_i
ightarrow B_{i+1}) 连边,容量给出。
有 (m) 对 (A_i
ightarrow B_j) 有边,容量给出。
你需要先求出原图从 (A_1) 到 (B_n) 的最大流,然后有 (q) 次操作,每次操作给出 (i),先修改 (A_i
ightarrow A_{i+1}) 的边的容量,然后询问从 (A_1) 到 (B_n) 的最大流。
(2leq n,mleq 2 imes 10^5),容量( leq 10^9)。
(n,mleq 2 imes 10^5)。
思路
最大流看着就恶心,考虑求最小割。
显然对于所有 (A_i o A_{i+1}) 的边,最多只会被割掉一条,否则更后面的那条根本没有必要割。(B_i o B_{i+1}) 的边同理也只会割掉一条。
记 (a_i) 表示 (A_i o A_{i+1}) 的边权,(b_i) 表示 (B_i o B_{i+1}) 的边权,那么假设我们要割 (A_i o A_{i+1}) 的边,最小割为
我们发现无论 (a_i) 怎么修改,它匹配的 (b_j) 都是不变的。所以我们可以先求出对于每一个 (a_i) 匹配哪一个 (b_j)。
维护一棵线段树,区间 ([l,r]) 维护当前匹配 (b_{l}sim b_r) 的最小代价。从小到大枚举 (i),把所有 (c_{i,j}) 的贡献插入线段树,然后求全局最小值即可。对于每一次询问只需要维护一个 multiset 就行了。
注意因为 (a) 和 (b) 可能会不割,所以我们需要加入边 (A_n o A_{n+1}) 和 (B_0 o B_1)。流量都是 (0)。
时间复杂度 (O((Q+n)log n))。
代码
#include <bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int N=200010;
int n,m,Q,a[N],b[N];
ll mins[N];
vector<pair<int,int> > c[N];
multiset<ll> s;
struct SegTree
{
ll minn[N*4],lazy[N*4];
void pushdown(int x)
{
if (lazy[x])
{
minn[x*2]+=lazy[x]; lazy[x*2]+=lazy[x];
minn[x*2+1]+=lazy[x]; lazy[x*2+1]+=lazy[x];
lazy[x]=0;
}
}
void update(int x,int l,int r,int ql,int qr,ll v)
{
if (ql<=l && qr>=r)
return (void)(minn[x]+=v,lazy[x]+=v);
pushdown(x);
int mid=(l+r)>>1;
if (ql<=mid) update(x*2,l,mid,ql,qr,v);
if (qr>mid) update(x*2+1,mid+1,r,ql,qr,v);
minn[x]=min(minn[x*2],minn[x*2+1]);
}
}seg;
int main()
{
scanf("%d%d%d",&n,&m,&Q);
for (int i=1;i<n;i++)
{
scanf("%d%d",&a[i],&b[i+1]);
seg.update(1,1,n,i+1,i+1,b[i+1]);
}
for (int i=1,x,y,z;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
c[x].push_back(mp(y,z));
}
for (int i=1;i<=n;i++)
{
for (int j=0;j<c[i].size();j++)
seg.update(1,1,n,1,c[i][j].fi,c[i][j].se);
mins[i]=seg.minn[1];
s.insert(a[i]+mins[i]);
}
cout<<*s.begin()<<"
";
while (Q--)
{
int x,y;
scanf("%d%d",&x,&y);
s.erase(s.find(a[x]+mins[x]));
a[x]=y; s.insert(a[x]+mins[x]);
cout<<*s.begin()<<"
";
}
return 0;
}