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

Problem

【SHOI2003】Pacman 吃豆豆

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;64\;MB}$

Description

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

Input

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

Output

仅有一行包含一个整数，即两个$\mathrm{PACMAN}$加起来最多能吃掉的豆豆数量

Sample Input

8
8 1
1 5
5 7
2 2
7 8
4 6
3 3
6 4

Sample Output

7

HINT

$N \le 2000$
样例解释


标签：费用流

Solution

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

• 源点拆成两个点$S$和$SS$
  $S\to SS$ 流量$2$ 费用$0$
• 把每个点拆成$i$和$i'$
  $SS\to i$ 流量$2$ 费用$0$
  $i'\to T$ 流量$2$ 费用$0$
  $i\to i'$ 流量$1$ 费用$1$
  $i\to i'$ 流量$1$ 费用$0$
• 可连边的相邻两点$i$和$j$间有
  $i'\to j$ 流量$2$ 费用$0$

最后跑大费流即可。

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;
}