BZOJ1930 [Shoi2003]pacman 吃豆豆 费用流

题目大意：在二维平面上有若干个点，求出两条不相交的二维LIS,使得上面包含的点的数目最多。

思路1：暴力建图

注意到不相交这个条件根本没用，画图可以发现如果相交的话，我们总可以通过交换一些点使得两个序列不相交。

那么问题转化为求出两个没有公共点的上升子序列，使得长度之和最大。

对于这种情况我们利用最大费用流求解。

设（a,b）分别表示一条有向边的流量和费用。

S->S' (2,0)

S'->x(1,0),x'->T(1,0)(1<=x<=n)

x->x' (1,1) 表示加上这个点会造成1的费用，点权限制为1表示只能出现一次

p'->q(1,0)条件是p.x<=q.x&&p.y<=q.y,表示q可以出现在p的后面，也就是说1的流量能从p流过产生费用后，再流到q.

但是这样建模的最大边数可以卡到O(n^2),只能得到70分。

思路2：优化

上述建模的瓶颈在于p'->q之间的边数太多，存在大量冗余。

我们不妨考虑将所有点按照(x,y)二元组排序。

然后若两个点之间存在某一个点使得这三个点依次能够构成一个上升子序列，则这两个点之间不连边。

但是这样的话，有可能两条流量都想要经过某个点，所以我们在每个点的入点和出点之间加上一条流量为2的边，使得这两条流量可以通过。

详细的细节自己看代码。

新技能get:允许带负权边的ZKW费用流！！

Code(spfa+多路增广):

#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <climits>
#include <iostream>
#include <algorithm>
using namespace std;
 
#define INF 0x3f3f3f3f
 
#define N 2010
queue<int> q;
int Edges = 0;
struct Solver {
    int head[N<<1], next[N*N], end[N*N], flow[N*N], cost[N*N], ind;
    int d[N<<1];
    bool inq[N<<1], vis[N<<1];
    void reset() {
        ind = 0;
        memset(head, -1, sizeof head);
    }
    void addedge(int a, int b, int _f, int _c) {
        int q = ind++;
        end[q] = b;
        next[q] = head[a];
        head[a] = q;
        flow[q] = _f;
        cost[q] = _c;
    }
    void make(int a, int b, int _f, int _c) {
        addedge(a, b, _f, _c);
        addedge(b, a, 0, -_c);
    }
    bool spfa(int S, int T) {
        memset(d, -1, sizeof d);
        d[S] = 0;
        inq[S] = 1, q.push(S);
        int i, j;
        while(!q.empty()) {
            i = q.front();
            q.pop();
            inq[i] = 0;
            for(j = head[i]; j != -1; j = next[j]) {
                if (flow[j] && d[end[j]] < d[i] + cost[j]) {
                    d[end[j]] = d[i] + cost[j];
                    if (!inq[end[j]]) {
                        inq[end[j]] = 1;
                        q.push(end[j]);
                    }
                }
            }
        }
        return d[T] != -1;
    }
    int Getflow(int p, int S, int T, int maxflow) {
        if (p == T)
            return maxflow;
        vis[p] = 1;
        int last = maxflow;
        for(int j = head[p]; j != -1; j = next[j]) {
            if (flow[j] && d[p] + cost[j] == d[end[j]] && (end[j] == T || !vis[end[j]])) {
                int to = Getflow(end[j], S, T, last > flow[j] ? flow[j] : last);
                flow[j] -= to;
                flow[j ^ 1] += to;
                last -= to;
                if (!last)
                    return maxflow;
            }
        }
        return maxflow - last;
    }
    int Maxcost(int S, int T) {
        int res = 0;
        while(spfa(S, T)) {
            memset(vis, 0, sizeof vis);
            res += Getflow(S, S, T, INF) * d[T];
        }
        return res;
    }
}G;
 
struct Node {
    int x, y;
    void read() {
        scanf("%d%d", &x, &y);
    }
    bool operator < (const Node &B) const {
        return x < B.x || (x == B.x && y < B.y);
    }
}S[N];
 
#define f(x) (x<<1)
#define g(x) (x<<1^1)
int main() {
    int n;
    scanf("%d", &n);
     
    register int i, j;
    for(i = 1; i <= n; ++i)
        S[i].read();
    sort(S + 1, S + n + 1);
     
    G.reset();
    G.make(0, 1, 2, 0);
    for(i = 1; i <= n; ++i)
        G.make(1, f(i), 1, 0), G.make(g(i), 2 * n + 2, 1, 0), G.make(f(i), g(i), 1, 1), G.make(f(i), g(i), 1, 0);
     
    for(i = 1; i <= n; ++i) {
        int Min = INF;
        for(j = i + 1; j <= n; ++j) {
            if (S[j].y < Min && S[j].y >= S[i].y)
                G.make(g(i), f(j), 2, 0);
            if (S[j].y >= S[i].y)
                Min = min(Min, S[j].y);
        }
    }
     
    printf("%d", G.Maxcost(0, 2 * n + 2));
     
    return 0;
}

Code2:ZKW费用流

#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <climits>
#include <iostream>
#include <algorithm>
using namespace std;
 
#define INF 0x3f3f3f3f
 
#define N 2010
queue<int> q;
int Edges = 0;
struct Solver {
    int head[N<<1], next[N*N], end[N*N], flow[N*N], cost[N*N], ind;
    int d[N<<1], slack[N<<1], used[N<<1], id;
    bool inq[N<<1];
    void reset() {
        ind = 0;
        id = 1;
        memset(used, 0, sizeof used);
        memset(head, -1, sizeof head);
    }
    void addedge(int a, int b, int _f, int _c) {
        int q = ind++;
        end[q] = b;
        next[q] = head[a];
        head[a] = q;
        flow[q] = _f;
        cost[q] = _c;
    }
    void make(int a, int b, int _f, int _c) {
        addedge(a, b, _f, _c);
        addedge(b, a, 0, -_c);
    }
    void spfa(int S, int T) {
        memset(d, 0x3f, sizeof d);
        d[S] = 0;
        inq[S] = 1, q.push(S);
        int i, j;
        while(!q.empty()) {
            i = q.front();
            q.pop();
            inq[i] = 0;
            for(j = head[i]; j != -1; j = next[j]) {
                if (flow[j]) {
                    if (d[end[j]] > d[i] + cost[j]) {
                        d[end[j]] = d[i] + cost[j];
                        if (!inq[end[j]]) {
                            inq[end[j]] = 1;
                            q.push(end[j]);
                        }
                    }
                }
            }
        }
        for(i = S; i <= T; ++i)
            d[i] = d[T] - d[i];
    }
    bool Newlabel(int S, int T) {
        int i, Min = INF;
        for(i = S; i <= T; ++i)
            if (used[i] != id && slack[i] < Min)
                Min = slack[i];
        if (Min == INF) return 0;
        for(i = S; i <= T; ++i)
            if (used[i] == id)
                used[i] = -1, d[i] += Min;
        return 1;
    }
    int Getflow(int p, int T, int maxflow) {
        if (p == T)
            return maxflow;
        used[p] = id;
        for(int j = head[p]; j != -1; j = next[j]) {
            if (flow[j] && used[end[j]] != id && d[p] == d[end[j]] + cost[j]) {
                int to = Getflow(end[j], T, maxflow > flow[j] ? flow[j] : maxflow);
                if (to) {
                    flow[j] -= to;
                    flow[j ^ 1] += to;
                    return to;
                }
            }
            else if (flow[j])
                slack[end[j]] = min(slack[end[j]], d[end[j]] + cost[j] - d[p]);
        }
        return 0;
    }
    int Mincost(int S, int T) {
        int res = 0, get;
        spfa(S, T);
        do {
            memset(slack, 0x3f, sizeof slack);
            while((get = Getflow(S, T, INF)))
                res += get * d[S], ++id;
        }while(Newlabel(S, T)); 
        return res;
    }
}G;
 
struct Node {
    int x, y;
    void read() {
        scanf("%d%d", &x, &y);
    }
    bool operator < (const Node &B) const {
        return x < B.x || (x == B.x && y < B.y);
    }
}S[N];
 
#define f(x) (x<<1)
#define g(x) (x<<1^1)
int main() {
    int n;
    scanf("%d", &n);
     
    register int i, j;
    for(i = 1; i <= n; ++i)
        S[i].read();
    sort(S + 1, S + n + 1);
     
    G.reset();
    G.make(0, 1, 2, 0);
    for(i = 1; i <= n; ++i)
        G.make(1, f(i), 1, 0), G.make(g(i), 2 * n + 2, 1, 0), G.make(f(i), g(i), 1, -1), G.make(f(i), g(i), 1, 0);
     
    for(i = 1; i <= n; ++i) {
        int Min = INF;
        for(j = i + 1; j <= n; ++j) {
            if (S[j].y < Min && S[j].y >= S[i].y)
                G.make(g(i), f(j), 2, 0);
            if (S[j].y >= S[i].y)
                Min = min(Min, S[j].y);
        }
    }
     
    printf("%d", -G.Mincost(0, 2 * n + 2));
     
    return 0;
}