NC20951（网络优化 ）

感受

思路

#include <bits/stdc++.h>
#define ls o << 1
#define rs o << 1 | 1
using namespace std;
typedef long long ll;
const int maxn = 3e4 + 10;
const int maxm = 2e6 + 10;
const int inf = 1e9;
int dfn;
int T[maxn << 2];
struct MaxFlow{
    int head[maxn], dep[maxn], que[maxn];///(L, R] 先进先出
    int cnt, s, t, n, L, R;
    struct edge{
        int v, nex; ll w;
    }e[maxm];
    void Init(){
        cnt = 0;
        memset(head, -1, sizeof(head));
    }
    void init(int _s, int _t){
         s = _s; t = _t; n = t + 1;

    }
    void add(int u, int v, ll w){
        e[cnt] = (edge){v, head[u], w}; head[u] = cnt++;
        e[cnt] = (edge){u, head[v], 0}; head[v] = cnt++;
    }
    inline bool bfs(){
        for(int i = 0; i <= n; i++) dep[i] = 0;
        que[dep[s] = R = 1] = s; L = 0;
        while(L < R){
            int u =que[++L], v;
            for(int i = head[u]; ~i; i = e[i].nex){
                v = e[i].v;
                if(e[i].w > 0 && !dep[v]){
                    dep[v] = dep[u] + 1; que[++R] = v;
                    if(v == t) return true;
                }
            }
        }
        return false;
    }
    ll dfs(int u, ll nf){
        if(u == t) return nf;
        ll res = 0;
        int v;
        for(int i = head[u]; nf && ~i; i = e[i].nex){
            v = e[i].v;
            if(dep[v] != dep[u] + 1 || !e[i].w) continue;
            ll tf = dfs(v, min(nf, e[i].w));
            res += tf; nf -= tf;
            e[i].w -= tf; e[i ^ 1].w += tf;
        }
        if(!nf) dep[u] = 0;
        return res;
    }///走到u处时, 流向u的最大流量和    res表示实际可以流向u的流量和（保证子节点可以流通）
    ll run(){
        ll flow = 0;
        while(bfs()){
            flow += dfs(s, inf);
        }
        return flow;
    }
}MF;
void build(int o, int l, int r){
    T[o] = ++dfn;
    if(l == r){
        MF.add(0, T[o], 1);
        return ;
    }
    int mid = (l + r) / 2;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    MF.add(T[ls], T[o], mid - l + 1);
    MF.add(T[rs], T[o], r - mid);
}
void update(int o, int l, int r, int x, int y, int v){
    if(l >= x && y >= r){
        MF.add(T[o], v, r - l + 1);
        return ;
    }
    int mid = (l + r) / 2;
    if(mid >= x) update(ls, l, mid, x, y, v);
    if(y > mid) update(rs, mid + 1, r, x, y, v);
}
int main(){
    int n, m;
    while(scanf("%d%d", &n, &m) != EOF){
        MF.Init();
        dfn = 0;
        build(1, 1, n);
        MF.init(0, dfn + m + 1);
        int l, r, v;
        for(int i = 1; i <= m; i++){
            scanf("%d%d%d", &l, &r, &v);
            update(1, 1, n, l, r, dfn + i);
            MF.add(dfn + i, MF.t, v);
        }
        printf("%d\n", MF.run());
    }
    return 0;
}