• https://darkbzoj.cc/problem/3681

网络流建模上比上题要简单。
函数式线段树方面需要线段树合并。
总之还是比上一题简单。

darkbzoj 不支持 cpp14，无法方便的使用 atl。。。（至少我不知道怎么改。。。）
值得注意的是对权值重复节点的处理，我们可以在叶子位置动态创建新的节点，
把旧叶子都包含在内，不影响复杂度。

另外对于之前的这类树上线段树合并问题，merge 的时候我们可以破坏掉之前的状态，覆盖式更新而不去 new_node() 以减少内存开支。
但是这个题里我们必须区别出这些状态（建图的时候会 query 到），所以还是老实的每次都 new_node() 为好。。。

const int N = int(1e4) + 9;

struct Network_Flow{
const static int N = int(1e6) + 6, M = 2*N;
int D[N], hd[N], suc[M], to[M], cap[M];
int n, m, s, t;

inline void add_edge(int x, int y, int c){
    suc[m] = hd[x], hd[x] = m, to[m] = y, cap[m++] = c,
    suc[m] = hd[y], hd[y] = m, to[m] = x, cap[m++] = 0;
}

inline void add_edgee(int x, int y, int c){
    suc[m] = hd[x], hd[x] = m, to[m] = y, cap[m++] = c,
    suc[m] = hd[y], hd[y] = m, to[m] = x, cap[m++] = c;
}

#define v to[i]
#define c cap[i]
#define f cap[i^1]

bool bfs(){
    static int Q[N]; int cz = 0, op = 1;
    fill(D, D+n, 0), D[Q[0] = s] = 1; while (cz < op){
        int u = Q[cz++]; REP_G(i, u) if (!D[v]&&c){
            D[Q[op++]=v] = D[u]+1;
            if (v==t) return 1;
        }
    }
    return 0;
}

LL Dinitz(){
    LL z=0; while (bfs()){
        static int cur[N], pre[N];
        int u=s;pre[s]=-1;cur[s]=hd[s];while (~u){
#define i cur[u]
            if (u==t){
                int d=INF;for(u=s;u!=t;u=v)checkMin(d,c);
                z+=d;for(u=s;u!=t;u=v)f+=d,c-=d;u=s;
            }
#undef i
            int i;for(i=cur[u];i;i=suc[i])if(D[u]+1==D[v]&&c){cur[u]=i,cur[v]=hd[v],pre[v]=u,u=v;break;}
            if (!i)D[u]=0,u=pre[u];
        }
    }
    return z;
}
#undef f
#undef c
#undef v
} G;



int T[N], H[N]; VI adj[N];
int n, m;

namespace Chairman_Tree {
#define lx c[0][x]
#define rx c[1][x]
#define ly c[0][y]
#define ry c[1][y]
#define ml ((l+r)>>1)
#define mr (ml+1)
#define lc lx, l, ml
#define rc rx, mr, r
    const int NN = 100*N;
    int c[2][NN]; int tot;
    int pp;
    int new_node() {
        return ++tot;
    }
    int new_node(int y) {
        int x = ++tot; lx = ly; rx = ry;
        return x;
    }

    void Init(int &x, int l = 1, int r = n) {
        x = new_node();
        if (l == r) {
            G.add_edge(x, G.t, 1);
        } else {
            if (pp < mr) Init(lc);
            else Init(rc);
        }
    }

    int Merge(int x, int y, int l = 1, int r = n) {
        if (!x || !y) return x | y;
        if (l == r) {
            int z = new_node();
            c[0][z] = x;
            c[1][z] = y;
            return z;
        }
        x = new_node(x);
        lx = Merge(lx, ly, l, ml);
        rx = Merge(rx, ry, mr, r);
        return x;
    }

    void Query(int x, int l, int r, int a, int b, VI& L) {
        if (!x || b < l || r < a) return;
        if (a <= l && r <= b) {
            L.PB(x);
        } else {
            Query(lc, a, b, L);
            Query(rc, a, b, L);
        }
    }

} using namespace Chairman_Tree;

void dfs(int u = 1) {
    pp = H[u]; Init(T[u]);
    for (auto v: adj[u]) {
        dfs(v);
        T[u] = Merge(T[u], T[v]);
    }
}


int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

    RD(n, m); G.m = 2; G.s = n+m, G.t = n+m+1; tot = G.t;

    FOR_1(i, 2, n) adj[RD()].PB(i);
    REP_1(i, n) RD(H[i]); dfs();

    REP(i, m) {
        int l, r, d; RD(l, r, d); G.add_edge(G.s, i, RD());
        VI L; Query(T[d], 1, n, l, r, L);
        for (auto l: L) G.add_edge(i, l, INF);
    }

    FOR_1(x, G.t+1, tot) {
        if (lx) G.add_edge(x, lx, INF);
        if (rx) G.add_edge(x, rx, INF);
    }

    G.n = tot+1;
    cout << G.Dinitz() << endl;
}

Posted by xiaodao
Category: 日常