Codeforces

Luogu

分析

最大流似乎不太好求,可以考虑求最小割。

考虑给出的图的最小割的形态。容易发现我们只会割掉至多一条 $A$ 边、至多一条 $B$ 边。

假设我们割掉了 $(A_u,A_{u+1})$ 和 $(B_v,B_{v+1})$,则我们还应割掉所有满足 $i\leq u,j>v$ 的边 $(A_i,B_j)$。

假设 $(A_i,A_{i+1})$ 的边权为 $a_i$,$(B_i,B_{i+1})$ 的边权为 $b_i$,$(A_i,B_j)$ 的边权为 $w_{i,j}$,则我们需要求出

$$ \min_{1\leq u,v<n}\left\{a_u+b_v+\sum_{i\leq u,j>v}w_{i,j}\right\} $$

注意到修改仅会改 $a_i$,因此每个 $a_u$ 对应的 $b_v$ 是唯一且不变的,因此我们考虑先对于每个 $u$ 求出

$$ c_u=\min_{1\leq v<n}\left\{b_v+\sum_{i\leq u,j>v}w_{i,j}\right\} $$

维护一棵线段树,初始时第 $i$ 个位置的值为 $b_i$。然后从小到大枚举所有 $u$,并遍历 $A_u$ 的所有出边 $(A_u,B_v)$,然后在线段树上将 $[1,B_v]$ 位置加上 $w_{u,v}$。加完后线段树上的最小值就是 $c_u$。

现在问题变为求修改 $a_u$ 和求 $a_u+c_u$ 的最小值,直接线段树维护即可。

还有一个小问题是以上讨论的是 $A$ 边和 $B$ 边都割的情况,然而还有另外 $3$ 种情况。一种方便的解决方法是加两条边权为 $0$ 的边 $(A_n,A_{n+1})$ 和 $(B_0,B_1)$,这样子新图中都割的情况包含原图中其它 $3$ 种情况,然后就对了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,m,q;
ll a[N],b[N],c[N];
vector<pair<int,int> > E[N];

#define ls (o<<1)
#define rs (o<<1|1)
ll minv[N<<2],addv[N<<2];
inline void pushup(int o) { minv[o]=min(minv[ls],minv[rs]); }
inline void pushdown(int o) {
    if (addv[o]) {
        addv[ls]+=addv[o],minv[ls]+=addv[o];
        addv[rs]+=addv[o],minv[rs]+=addv[o];
        addv[o]=0;
    }
}
inline void build(int o,int l,int r,ll* s) {
    addv[o]=0;
    if (l==r) { minv[o]=s[l]; return; }
    int mid=(l+r)>>1;
    build(ls,l,mid,s),build(rs,mid+1,r,s);
    pushup(o);
}
inline void modify(int o,int l,int r,int ql,int qr,int w) {
    if (ql<=l&&r<=qr) { addv[o]+=w,minv[o]+=w; return; }
    int mid=(l+r)>>1; pushdown(o);
    if (ql<=mid) modify(ls,l,mid,ql,qr,w);
    if (qr>mid) modify(rs,mid+1,r,ql,qr,w);
    pushup(o);
}
#undef ls
#undef rs

int main() {
    n=read(),m=read(),q=read();
    for (re int i=1;i<n;++i) a[i]=read(),b[i+1]=read();
    a[n]=b[1]=0;
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read(),w=read();
        E[u].push_back(make_pair(v,w));
    }
    build(1,1,n,b);
    for (re int i=1;i<=n;++i) {
        for (auto v:E[i]) modify(1,1,n,1,v.first,v.second);
        c[i]=minv[1];
    }
    for (re int i=1;i<=n;++i) c[i]+=a[i];
    build(1,1,n,c); printf("%lld\n",minv[1]);
    while (q--) {
        int p=read(),w=read();
        modify(1,1,n,p,p,w-a[p]),a[p]=w;
        printf("%lld\n",minv[1]);
    }
    return 0;
}
最后修改:2020 年 01 月 14 日 08 : 05 PM