BZOJ 3218 a + b Problem 最大流 + 可持久化線段樹

這題目真的很吸引人233。

樣例不能複制真是可惜233。

題目的方格染色以及奇怪的節點讓我想起了以前看過的一篇博文，講最小割的。。

于是這道題就最小割。。。

http://blog.csdn.net/huanghongxun/article/details/50510013

↑這是新文章，CSDN好像不準從普通編輯器切換成markdown編輯器，必須要發新帖？

為什麼别人的程式都這麼快。。

應該不是這麼寫的吧。。

真的是痛苦。。

各種腦抽寫錯，程式重寫了2遍。。

原來SegTree的預設構造函數裡面包括了自增id，然而operator new裡面定義的大數組也會自增id。

然後不說占用了大量無用id，各種爆數組。。還奇怪為什麼會RE。。

有時候不能手賤，預設構造函數還是要謹慎一些。

代碼：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 8192, M = 262144, inf = 1000000000, EDGE = 1048576;
struct SegTree {
    static int timer;
    static void put_callback(SegTree *node, SegTree *new_node, int f);
    static void get_callback(SegTree *node, int x);
    SegTree *lc, *rc;
    int v, s;
    SegTree() { lc = rc = NULL; v = s = 0; }
    SegTree(SegTree *a, SegTree *b, int c) : lc(a), rc(b), v(c), s(++timer) {}
    void *operator new(size_t) {
        static SegTree pool[M], *C = pool;
        return C++;
    }
    SegTree *put(int l, int r, int t, int f) {
        int mid = l + r >> 1;
        SegTree *rt;
        if (l == r) rt = new SegTree(NULL, NULL, v + 1);
        else if (t <= mid) rt = new SegTree(lc->put(l, mid, t, f), rc, v + 1);
        else rt = new SegTree(lc, rc->put(mid + 1, r, t, f), v + 1);
        put_callback(this, rt, f);
        return rt;
    }
    void get(int l, int r, int ql, int qr, int x) {
        int mid = l + r >> 1;
        if (!v) return;
        if (ql == l && r == qr) {
            get_callback(this, x);
            return;
        }
        if (ql > mid) rc->get(mid + 1, r, ql, qr, x);
        else if (qr <= mid) lc->get(l, mid, ql, qr, x);
        else lc->get(l, mid, ql, mid, x), rc->get(mid + 1, r, mid + 1, qr, x);
    }
} *tree[N];
int SegTree::timer = 0;
struct MaxFlow {
    int s, t, cnt;
    int head[M], next[EDGE], w[EDGE], to[EDGE], level[M];
    MaxFlow(int _s, int _t) : cnt(0), s(_s), t(_t) {
        memset(head, -1, sizeof head);
    }
    void add(int u, int v, int c) {
        next[cnt] = head[u]; to[cnt] = v; w[cnt] = c; head[u] = cnt++;
        next[cnt] = head[v]; to[cnt] = u; w[cnt] = 0; head[v] = cnt++;
    }
    bool bfs() {
        static int q[M];
        memset(level, -1, sizeof level);
        int f = 0, r = 0;
        q[r++] = s; level[s] = 0;
        while (f < r) {
            int u = q[f++];
            for (int i = head[u]; i != -1; i = next[i])
                if (w[i] > 0 && level[to[i]] == -1) {
                    level[to[i]] = level[u] + 1;
                    q[r++] = to[i];
                }
        }
        return level[t] != -1;
    }
    int dfs(int k, int low) {
        if (k == t) return low;
        int res = 0, tmp, i;
        for (i = head[k]; i != -1 && res < low; i = next[i])
            if (level[to[i]] == level[k] + 1 && w[i] > 0) {
                tmp = dfs(to[i], min(low - res, w[i]));
                w[i] -= tmp;
                w[i^1] += tmp;
                res += tmp;
            }
        if (!res) level[k] = -1;
        return res;
    }
    ll solve() {
        ll ans = 0;
        while (bfs()) ans += dfs(s, inf);
        return ans;
    }
} *maxflow;

void SegTree::put_callback(SegTree *t, SegTree *nt, int f) {
    maxflow->add(f, nt->s, inf);
    maxflow->add(t->s, nt->s, inf);
}
void SegTree::get_callback(SegTree *t, int x) {
    maxflow->add(t->s, x, inf);
}

int main() {
    #define p2(i) ((i)*2)
    #define p1(i) ((i)*2-1)
    int i, a, b, w, l, r, p, n;
    ll ans = 0;
    scanf("%d", &n);
    maxflow = new MaxFlow(0, M - 1);
    SegTree::timer = p2(n);
    tree[0] = new SegTree(NULL, NULL, 0);
    tree[0]->lc = tree[0]->rc = tree[0];
    for (i = 1; i <= n; i++) {
        scanf("%d%d%d%d%d%d", &a, &b, &w, &l, &r, &p);
        maxflow->add(maxflow->s, p1(i), w);
        maxflow->add(p1(i), maxflow->t, b);
        tree[i] = tree[i - 1]->put(0, inf, a, p1(i));
        tree[i - 1]->get(0, inf, l, r, p2(i));
        maxflow->add(p2(i), p1(i), p);
        ans += w + b;
    }
    printf("%lld", ans - maxflow->solve());

    return 0;
}
           

随便寫了個資料生成器，真是不寫沒法調試。。

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;

int random(int sz) {
    return ((double)rand())/RAND_MAX*sz+1;
}

int main() {
    freopen("input.in", "w", stdout);
    int n = 5000, maxA = 1000000000, maxV = 200000, maxP = 300000;
    srand(time(NULL));
    printf("%d\n", n);
    for (int i = 1; i <= n; i++) {
        int c = random(maxA), x = random(min(c, maxA - c));
        printf("%d %d %d %d %d %d\n", random(maxA), random(maxV), random(maxV), c - x, c + x, random(maxP));
    }
    
    return 0;
}
           

latex大法好

http://blog.csdn.net/regina8023/article/details/42873403

http://www.cnblogs.com/snake-hand/p/3144807.html

http://blog.csdn.net/PoPoQQQ/article/details/42557217