BZOJ1930【SHOI2003】Pacman 吃豆豆 <费用流>

Problem

【SHOI2003】Pacman 吃豆豆

Description

两个吃豆豆。一开始的时候，都在坐标原点的左下方，豆豆都在右上方。走到豆豆处就会吃掉它。行走的路线很奇怪，只能向右走或者向上走，他们行走的路线不可以相交。请你帮这两个计算一下，他们俩加起来最多能吃掉多少豆豆。

Input

第一行为一个整数，表示豆豆的数目。接下来行，每行一对正整数，表示第个豆豆的坐标。任意两个豆豆的坐标都不会重合。

Output

仅有一行包含一个整数，即两个加起来最多能吃掉的豆豆数量

Sample Input

Sample Output

HINT

样例解释

标签：费用流

Solution

貌似是可以用肝的。
费用流建模细节挺多。
首先可以发现不相交时废话。若穿过则互换名字即可。
由于点数很多，所以不能两两连边，发现只需要把按和排序后相邻两点连边即可。
首先需要限制每个点的流量，需要将每个点拆成两个点，连边限流。
这里由于两条线可以经过同一个点，但贡献只算一个，则需要连两条边，流量均为，而费用则是一条为另一条为。
注意源点也需要限制的流量，即需要把源点拆成两个点，中间连流量费用的边。
相邻两点间连流量为费用为的边。
总结建图：

源点拆成两个点和
流量费用
把每个点拆成和
流量费用
流量费用
流量费用
流量费用
可连边的相邻两点和间有
流量费用

最后跑大费流即可。

Code

#include <bits/stdc++.h>
#define MAX_N 5000
#define MAX_M 500000
#define INF 0x7f7f7f7f
using namespace std;
struct P {int x, y;} p[MAX_N+5];
int n, s, ss, t, cnt, pr[MAX_N+5], cr[MAX_N+5], mxf, mxc;
struct node {int v, c, w, nxt;} E[MAX_M+5];
void init() {s = 0, ss = n*2+1, t = n*2+2, memset(pr, -1, sizeof pr);}
bool cmp (const P &a, const P &b) {return a.x == b.x ? a.y < b.y : a.x < b.x;}
void insert(int u, int v, int c, int w) {E[cnt] = (node){v, c, w, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c, int w) {insert(u, v, c, w), insert(v, u, 0, -w);}
bool SPFA() {
    queue <int> que;	bool inq[MAX_N+5];	int d[MAX_N+5], cr[MAX_N+5];
    memset(inq, false, sizeof inq), memset(cr, -1, sizeof cr);
    memset(d, -1, sizeof d);	d[s] = 0, que.push(s), inq[s] = true;
    while (!que.empty()) {
        int u = que.front();	que.pop(), inq[u] = false;
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c, w = E[i].w;
            if (c && d[u]+w > d[v]) {
                d[v] = d[u]+w, cr[v] = i;
                if (!inq[v]) que.push(v), inq[v] = true;
            }
        }
    }
    if (d[t] <= 0) return false;	int flow = INF;
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) flow = min(flow, E[i].c);
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) E[i].c -= flow, E[i^1].c += flow;
    mxf += flow, mxc += d[t];	return true;
}
int main() {
    scanf("%d", &n);	init(), addedge(s, ss, 2, 0);
    for (int i = 1; i <= n; i++) addedge(ss, i, 2, 0), addedge(i+n, t, 2, 0);
    for (int i = 1; i <= n; i++) addedge(i, i+n, 1, 1), addedge(i, i+n, 1, 0);
    for (int i = 1; i <= n; i++) scanf("%d%d", &p[i].x, &p[i].y);	sort(p+1, p+n+1, cmp);
    for (int i = 1, mi = INF; i <= n; i++, mi = INF) for (int j = i+1; j <= n; j++)
        if (p[i].y <= p[j].y && p[j].y <= mi) addedge(i+n, j, 2, 0), mi = p[j].y;
    while (SPFA()) ;	return printf("%d", mxc), 0;
}