Description

小园丁 Mr. S 负责看管一片田野,田野可以看作一个二维平面。田野上有$n$棵 许愿树,编号 $1,2,3, ⋯ , n$ ,每棵树可以看作平面上的一个点,其中第$i$棵树 ($1 ≤ i ≤ n$) 位于坐标 $(x_i, y_i)$ 。任意两棵树的坐标均不相同。

老司机 Mr. P 从原点 $(0,0)$ 驾车出发,进行若干轮行动。每一轮,Mr. P 首先选择任意一个满足以下条件的方向:

1.为左、右、上、左上 45°、右上 45°五个方向之一。

2.沿此方向前进可以到达一棵他尚未许愿过的树。

完成选择后,Mr. P 沿该方向直线前进,必须到达该方向上距离最近的尚未 许愿的树,在树下许愿并继续下一轮行动。如果没有满足条件的方向可供选择, 则停止行动。他会采取最优策略,在尽可能多的树下许愿。若最优策略不唯一, 可以选择任意一种。

不幸的是,小园丁 Mr. S 发现由于田野土质松软,老司机 Mr. P 的小汽车在 每轮行进过程中,都会在田野上留下一条车辙印,一条车辙印可看作以两棵树(或 原点和一棵树)为端点的一条线段。

在 Mr.P之后,还有很多许愿者计划驾车来田野许愿,这些许愿者都会像Mr. P 一样任选一种最优策略行动。Mr.S认为非左右方向(即上、左上 45°、右 上 45°三个方向)的车辙印很不美观,为了维护田野的形象,他打算租用一些轧路机,在这群许愿者到来之前夯实所有“可能留下非左右方向车辙印”的地面。“可能留下非左右方向车辙印”的地面应当是田野上的若干条线段,其中每条线 段都包含在某一种最优策略的行进路线中。每台轧路机都采取满足以下三个条件的工作模式:

1.从原点或任意一棵树出发。

2.只能向上、左上 45°、右上 45°三个方向之一移动,并且只能在树下改变方向或停止。

3.只能经过“可能留下非左右方向车辙印”的地面,但是同一块地面可以 被多台轧路机经过。

现在 Mr. P 和 Mr. S 分别向你提出了一个问题:

1.请给 Mr.P 指出任意一条最优路线。

2.请告诉 Mr.S 最少需要租用多少台轧路机。

Input

第 1 行包含 1 个正整数$n, n \le 5 \times 10^4$ ,表示许愿树的数量。

接下来 $n$ 行,第 $i + 1$ 行包含 $2$ 个整数 $x_i , y_i$ ,中间用单个空格隔开,表示第$i$棵许愿树的坐标。

保证最优路线唯一,或者 $y_i = Y$ 的树不超过 $10^3$ 棵。

Output

包括 $3$ 行。

第 $1$ 行输出 $1$ 个整数 $m$ ,表示 Mr. P 最多能在多少棵树下许愿。

输出文件的第 $2$ 行输出 $m$ 个整数,相邻整数之间用单个空格隔开,表示 Mr.P 应该依次在哪些树下许愿。

输出文件的第 $3$ 行输出 $1$ 个整数,表示 Mr. S 最少需要租用多少台轧路机。

对于每个测试点,若输出文件的第 $1$ 行正确,得到该测试点 $20\%$ 的分数;若输出文件的前两行正确,得到该测试点 $40\%$ 的分数;若输出文件完全正确,得到该测试点 $100\%$ 的分数。

Solution

前两问还是比较简单的。考虑DP,将点按主对角线,副对角线和$x$轴排序,可以找到它在非水平方向的后继。而水平方向的转移是可以直接算的,左右各扫一遍即可。由于要输出路径以及第三问的需要,需要记录转移的所有前驱。

对于第三问,首先根据记录的转移信息可以找到所有非左右方向的车辙印。考虑网络流,一条车辙印看作一条边,它至少被经过一次,因此下界为$1$,上界为$+\infty$,记做$(1, +\infty)$。然后源点向所有点连$(0, +\infty)$的边,所有点向汇点连$(0, +\infty)$的边,那么答案就是该网络的最小可行流。

如何求有上下界的网络流呢?建立超级源汇点$S, T$(不是原图中的源点和汇点),对于一条边$(low, high)$,若它由$u$指向$v$,则连边$S$到$v$,其流量为$low$,再连边$u$到$T$,流量上限相同,而原来那条边的流量上限变为$high - low$。这样做是因为$u$至少会流出$low$的流量,$v$同理。而这样我们就实现了上下界网络流的转化。

在原图没有源汇的情况下,用上述方法建图跑最大流,若满流(即流量为$\sum low$),则说明找到了可行流,利用残量网络可以得到一组可行解;否则无解(此时下界无法满足)。有源汇时(设其为$s, t$),从$t$到$s$连一条$+\infty$的边,使其也满足流量平衡即可。

而求最小可行流时,我们需要将$t$到$s$的边去掉,再从$t$到$s$跑最大流(将尽量多的流量退回去),注意到此时我们不会改变与$S, T$相连的边的流量,因此下界始终是满足的。记第一次最大流时$t$到$s$的边的流量为$f$,第二次网络流的答案为$f’$,那么答案就是$f - f’$。最大可行流是类似的,只是第二次网络流要从$s$到$t$做。

回到原题,由于这题中是一定有解的,我们实际上只需要在不连$t$到$s$的情况下只做$S$到$T$的网络流,则答案就是满流流量减去这次网络流的答案。

Source

#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
#include <vector>

#define For(i, j, k) for(int i = j; i <= k; i++)
#define Forr(i, j, k) for(int i = j; i >= k; i--)
#define Set(i, v) memset(i, v, sizeof i)
#define pb push_back

using namespace std;

const int N = 50010, M = 1000010;
const int oo = 1 << 20;

int n;

struct Point{
	int x, y, id, idx;
}P[N];

bool Vertical(Point A, Point B){
	return A.y < B.y || (A.y == B.y && A.x < B.x);
}

bool Horizontal(Point A, Point B){
	return A.x < B.x || (A.x == B.x && A.y < B.y);
}

bool Main_Diagonal(Point A, Point B){
	return A.y - A.x < B.y - B.x || (A.y - A.x == B.y - B.x && A.y < B.y);
}

bool Counter_Diagonal(Point A, Point B){
	return A.x + A.y < B.x + B.y || (A.x + A.y == B.x + B.y && A.y < B.y);
}

vector<int> suc[N], prec[N][2];
int dp[N][2], pre[N][2];

inline void Add(int x, int y){
	suc[x].pb(y);
}

void init(){
	P[0] = (Point){0, 0, 0, 0};
	
	sort(P, P + n + 1, Vertical);
	For(i, 0, n) P[i].id = i;

	sort(P, P + n + 1, Horizontal);
	For(i, 0, n - 1) if(P[i + 1].x == P[i].x) Add(P[i].id, P[i + 1].id);

	sort(P, P + n + 1, Main_Diagonal);
	For(i, 0, n - 1) if(P[i + 1].y - P[i + 1].x == P[i].y - P[i].x) Add(P[i].id, P[i + 1].id);

	sort(P, P + n + 1, Counter_Diagonal);
	For(i, 0, n - 1) if(P[i + 1].y + P[i + 1].x == P[i].y + P[i].x) Add(P[i].id, P[i + 1].id);

	sort(P, P + n + 1, Vertical);
	For(i, 0, n) dp[i][0] = dp[i][1] = -1e9;
}

int lbd[N], rbd[N];

void Print(int x, bool fst = false){
	if(!x) return;
	int y = pre[x][1];
	Print(pre[y][0]);
	if(x != y){
		if(y < x){
			Forr(i, y, lbd[x]) printf("%d ", P[i].idx);
			For(i, y + 1, x - 1) printf("%d ", P[i].idx);
		}
		else{
			For(i, y, rbd[x]) printf("%d ", P[i].idx);
			Forr(i, y - 1, x + 1) printf("%d ", P[i].idx);
		}
	}
	printf("%d%c", P[x].idx, fst ? '\n' : ' ');
}

bool vis[N][2];
int st[N], top;

inline void update(int i, int j, int val, int k = -1){
	if(dp[i][j] == val){
		if(k >= 0) prec[i][j].pb(k);
		else For(u, 1, top) prec[i][j].pb(st[u]);
	}
	if(dp[i][j] < val){
		prec[i][j].clear();
		if(k >= 0) prec[i][j].pb(k), pre[i][j] = k;
		else For(u, 1, top) prec[i][j].pb(st[u]), pre[i][j] = st[u];
		dp[i][j] = val;
	}
}

void Find_Path(){
	init();

	dp[0][0] = 0;

	int l = 0, r = 0;
	while(l <= n){
		while(P[r + 1].y == P[l].y && r < n) ++r;

		int Maxval = -1e9;
		For(i, l, r) update(i, 1, dp[i][0], i), lbd[i] = l, rbd[i] = r;
		For(i, l, r){
			update(i, 1, Maxval + i - l);
			if(dp[i][0] > Maxval) Maxval = dp[i][0], st[top = 1] = i;
			else if(dp[i][0] == Maxval) st[++top] = i;
		}

		Maxval = -1e9, top = 0;
		Forr(i, r, l){
			update(i, 1, Maxval + r - i);
			if(dp[i][0] > Maxval) Maxval = dp[i][0], st[top = 1] = i;
			else if(dp[i][0] == Maxval) st[++top] = i;
		}

		For(i, l, r) For(j, 0, (int)suc[i].size() - 1){
			int u = suc[i][j];
			update(u, 0, dp[i][1] + 1, i);
		}

		l = ++r;
	}


	int ans = 0, end = 0;
	For(i, 0, n) if(dp[i][1] > ans) ans = dp[i][1], end = i;
	For(i, 0, n) if(dp[i][1] == ans) vis[i][1] = true;

	printf("%d\n", ans);
	Print(end, true);
}

struct Dinic{

	int Begin[N], Next[M], to[M], flow[M], e;
	int dis[N], cur[N];
	int S, T;

	void init(){
		e = 1;
		Set(Begin, 0);
	}

	void Add(int u, int v, int w){
		to[++e] = v, Next[e] = Begin[u], flow[e] = w, Begin[u] = e;
		to[++e] = u, Next[e] = Begin[v], flow[e] = 0, Begin[v] = e;
	}

	bool BFS(){
		Set(dis, 0);
		dis[S] = 1;
		queue<int> q;
		q.push(S);
		while(!q.empty()){
			int u = q.front(); q.pop();
			for(int i = Begin[u]; i; i = Next[i]){
				int v = to[i];
				if(flow[i] > 0 && !dis[v]){
					dis[v] = dis[u] + 1;
					q.push(v);
				}
			}
		}
		return dis[T];
	}

	int DFS(int o, int sum){
		if(!sum || o == T) return sum;
		int sumf = 0;
		for(int &i = cur[o]; i && sum; i = Next[i]){
			int u = to[i], f;
			if(flow[i] > 0 && dis[u] == dis[o] + 1 && (f = DFS(u, min(sum, flow[i])))){
				flow[i] -= f, flow[i ^ 1] += f;
				sum -= f, sumf += f;
			}
		}
		return sumf;
	}

	int MaxFlow(int _S, int _T){
		S = _S, T = _T;
		int ans = 0;
		while(BFS()){
			For(i, 0, n + 4) cur[i] = Begin[i];
			ans += DFS(S, oo);
		}
		return ans;
	}

}G;

int in[N], out[N];

void Calc_Flow(){
	G.init();

	int r = n, l = lbd[r];
	while(l){
		For(i, l, r) if(vis[i][1]) For(j, 0, (int)prec[i][1].size() - 1) 
			vis[prec[i][1][j]][0] = true;
		For(i, l, r) if(vis[i][0]) For(j, 0, (int)prec[i][0].size() - 1){
			int u = prec[i][0][j];
			G.Add(u, i, oo), ++out[u], ++in[i];
			vis[u][1] = true;
		}
		
		r = l - 1, l = lbd[r];
	} 
	
	int s = n + 1, t = n + 2;
	int S = n + 3, T = n + 4, ret = 0;

	For(i, 0, n) G.Add(s, i, oo), G.Add(i, t, oo);
	For(i, 0, n + 2) ret += in[i], G.Add(S, i, in[i]), G.Add(i, T, out[i]);

	printf("%d\n", ret - G.MaxFlow(S, T));
}

int main(){
	scanf("%d", &n);
	For(i, 1, n) scanf("%d%d", &P[i].x, &P[i].y), P[i].idx = i;

	Find_Path();
	Calc_Flow();
	return 0;
}