记录编号	401529	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2015]小园丁与老司机	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.730 s
提交时间	2017-05-02 21:50:10	内存使用	101.40 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e6+10;
int n,x[N],y[N];
vector<int> go[N],bk[N];
void add(int f,int t){
	go[f].push_back(t);
	bk[t].push_back(f);
}
bool cmp2(int a,int b){//right
	return y[a]==y[b]?x[a]<x[b]:y[a]<y[b];
}
bool cmp3(int a,int b){//up
	return x[a]==x[b]?y[a]<y[b]:x[a]<x[b];
}
bool cmp4(int a,int b){//left45
	return x[a]+y[a]==x[b]+y[b]?y[a]<y[b]:x[a]+y[a]<x[b]+y[b];
}
bool cmp5(int a,int b){//right45
	return x[a]-y[a]==x[b]-y[b]?y[a]<y[b]:x[a]-y[a]<x[b]-y[b];
}
struct edge{int f,t,g;}w[N];
int head[N],next[N],cnt=1;
void add(int f,int t,int g){
	w[++cnt]=(edge){f,t,g};
	next[cnt]=head[f];
	head[f]=cnt;
	w[++cnt]=(edge){t,f,0};
	next[cnt]=head[t];
	head[t]=cnt;
}
struct st{
	int x,i,df;
	st(int X=0,int DF=0){x=X;i=head[x];df=DF;}
}z[N];
int l[N],top,s,t,S,T,ans;
#define V z[top].x
#define E z[top].i
#define F z[top].df
void change(){
	int df=F;ans-=df;
	for (int i=top-1;i;i--){
		w[z[i].i].g-=df;
		w[z[i].i^1].g+=df;
		z[i].df-=df;
		if (!z[i].df) top=i;
	}
}
queue<int> Q;
void bfs(){
	for (int i=0;i<=T;i++) l[i]=0;
	l[S]=1;Q.push(S);
	while (!Q.empty()){
		int v=Q.front();Q.pop();
		if (l[T]) continue;
		for (int i=head[v];i;i=next[i])
		if (w[i].g&&!l[w[i].t])
			l[w[i].t]=l[v]+1,Q.push(w[i].t);
	}
}
bool dinic(){
	bfs();
	if (!l[T]) return 0;
	z[top=1]=st(S,1e9);
	while (top){
		if (V==T) change(),E=next[E];else
		if (!E) l[V]=0,top--,E=next[E];else
		if (w[E].g&&l[w[E].t]==l[V]+1)
			z[top+1]=st(w[E].t,min(F,w[E].g)),top++;
		else E=next[E];
	}
	return 1;
}
int dp[N],f[N],q[N],from_dp[N],from_f[N];
//dp[i]表示走到i,之后向上走最多经过的点数
//f[i]表示走到i,尚未左右移动时最多经过的点数(不含自己)
int que[N],size,rank[N],pre[N],suc[N];
void update(int *dp,int *from,int x,int p,int v){
	if (v>dp[x]) dp[x]=v,from[x]=p;
}
void work(){
	for (int i=1;i<=size;i++){
		rank[que[i]]=i;
		if (i>1) pre[que[i]]=que[i-1];
		if (i<size) suc[que[i]]=que[i+1];
	}
	for (int i=1,Max=-1e9,p=0;i<=size;i++){
		update(dp,from_dp,que[i],que[i],f[que[i]]+1);
		update(dp,from_dp,que[i],p,Max+i);
		if (f[que[i]]>Max) Max=f[p=que[i]];
	}
	for (int i=size,Max=-1e9,p=0;i;i--){
		update(dp,from_dp,que[i],p,Max+size-i+1);
		if (f[que[i]]>Max) Max=f[p=que[i]];
	}
	for (int i=1;i<=size;i++){
		int v=que[i];
		for (int i=go[v].size()-1;i>=0;i--)
			update(f,from_f,go[v][i],v,dp[v]);
	}
}
void solution(int p){//输出到达dp[p]的方案
	if (!p) return;
	int f=from_dp[p];
	solution(from_f[f]);
	printf("%d ",f);
	if (f==p) return;
	if (rank[f]<rank[p]){
		for (int i=pre[f];i;i=pre[i]) printf("%d ",i);
		for (int i=suc[f];i!=p;i=suc[i]) printf("%d ",i);
	}
	else{
		for (int i=suc[f];i;i=suc[i]) printf("%d ",i);
		for (int i=pre[f];i!=p;i=pre[i]) printf("%d ",i);
	}
	printf("%d ",p);
}
bool ok_dp[N],ok_f[N];
void add_edge(){
	for (int i=1,Min=1e9;i<=size;i++){
		if (ok_dp[que[i]]&&f[que[i]]+1==dp[que[i]]) ok_f[que[i]]=1;
		if (f[que[i]]==Min) ok_f[que[i]]=1;
		if (ok_dp[que[i]]) Min=min(Min,dp[que[i]]-size+i-1);
	}
	for (int i=size,Min=1e9;i>=0;i--){
		if (f[que[i]]==Min) ok_f[que[i]]=1;
		if (ok_dp[que[i]]) Min=min(Min,dp[que[i]]-i);
	}
	for (int i=1;i<=size;i++){
		int v=que[i];
		if (ok_f[v]){
			for (int i=bk[v].size()-1;i>=0;i--)
			if (dp[bk[v][i]]==f[v]){
				int u=bk[v][i];
				ok_dp[u]=1;
				add(u,v,1e9);
				ans++;
				add(t,v,1);
				add(u,s,1);
			}
		}
	}
}
void makegraph(){
	t=n+1;s=t+1;
	for (int i=0;i<=n;i++) add(s,i,1e9),add(i,t,1e9);
	for (int i=n;i>=0;){
		int flag=y[q[i]];
		size=0;
		while (i>=0&&y[q[i]]==flag) que[++size]=q[i--];
		add_edge();
	}
}
int main()
{
	freopen("farm.in","r",stdin);
	freopen("farm.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
	for (int i=0;i<=n;i++) q[i]=i;
	sort(q,q+n+1,cmp3);
	for (int i=0;i<n;i++)
		if (x[q[i]]==x[q[i+1]]) add(q[i],q[i+1]);
	sort(q,q+n+1,cmp4);
	for (int i=0;i<n;i++)
		if (x[q[i]]+y[q[i]]==x[q[i+1]]+y[q[i+1]]) add(q[i],q[i+1]);
	sort(q,q+n+1,cmp5);
	for (int i=0;i<n;i++)
		if (x[q[i]]-y[q[i]]==x[q[i+1]]-y[q[i+1]]) add(q[i],q[i+1]);
	sort(q,q+n+1,cmp2);
	for (int i=1;i<=n;i++) f[i]=dp[i]=-1e9;
	for (int i=0;i<=n;){
		int flag=y[q[i]];
		size=0;
		while (y[q[i]]==flag) que[++size]=q[i++];
		work();
	}
	int ans1=-1e9,p=0;
	for (int i=0;i<=n;i++)
		if (dp[i]>ans1) ans1=dp[p=i];
	printf("%d\n",ans1-1);
	for (int i=0;i<=n;i++)
		if (dp[i]==ans1) ok_dp[i]=1;
	solution(p);puts("");
	makegraph();
	S=t;T=s;
	while (dinic());
	printf("%d\n",ans);
	return 0;
}