「题解」「NOI2015」小园丁与老司机 farm

NOI2015 Day 2 T3,一道 网络流 的题目。

题目链接:Luogu P2304LibreOJ 2134BZOJ 4200UOJ 132、NOI2015 D2T3。

题目

题目描述

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

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

  1. 为左、右、上、左上 \(45^\circ\)、右上 \(45^\circ\) 五个方向之一。
  2. 沿此方向前进可以到达一棵他尚未许愿过的树。

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

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

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

  1. 从原点或任意一棵树出发。
  2. 只能向上、左上 \(45^\circ\)、右上 \(45^\circ\) 三个方向之一移动,并且只能在树下改变方向或停止。
  3. 只能经过“可能留下非左右方向车辙印”的地面,但是同一块地面可以被多台轧路机经过。

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

  1. 请给 Mr.P 指出任意一条最优路线。
  2. 请告诉 Mr.S 最少需要租用多少台轧路机。

数据范围

测试点编号\(n\) 的规模\(x _ i,y _ i\) 的规模备注
1\(n=5\)\(|x _ i|\leq 100\)
\(0<y _ i\leq 100\)
2\(n=10\)
3\(n=100\)\(|x _ i|\leq 10^4\)
\(0<y _ i\leq 10^4\)
4\(n=1000\)
5\(n=5000\)\(|x _ i|\leq 10^6\)
\(0<y _ i\leq 10^6\)
保证最优路线唯一
6
7\(n=5\times 10^4\)
8\(n=5000\)保证 \(y _ i\) 互不相同
9\(n=5\times 10^4\)
10
11\(n=5000\)保证对于任意整数 \(Y\),满足 \(y _ i=Y\) 的树不超过 \(1000\) 棵
存在一种最优解,使得轧路机不重复经过同一路面
12
13\(n=50000\)
14
15\(n=10^4\)\(|x _ i|\leq 10^9\)
\(0<y _ i\leq 10^9\)
保证对于任意整数 \(Y\),满足 \(y _ i=Y\) 的树不超过 \(1000\) 棵
16
17\(n=3\times 10^4\)
18
19\(n=5\times 10^4\)
20

对于所有数据,\(n\leq 5\times 10^4,|x _ i|\leq 10^9,0<y _ i\leq 10^9\)。

对于每一组数据:

  • 如果输出的第一行正确,那么你将得到该测试点 \(20\%\) 的分数;
  • 如果第二行也正确,那么你将再得到 \(20\%\) 的分数;
  • 第三行仍正确可以得到剩下的 \(60\%\) 的分数。

请注意,即使你的程序只能拿到部分分,也请完全按照格式输出,否则你的程序将被判为 \(0\) 分。

时空限制

题解

NOI2015 Day 2 T3,一道 网络流 的题目。

思路

建图

首先我们不难发现,如果点 \(i\) 与点 \(j\) 满足点 \(j\) 在点 \(i\) 的左上方 \(45^\circ\),那么一定满足
\[b=x _ i+y _ i\Rightarrow y _ j=x _ j+b\]

两点都在一条直线 \(y=-x+b\) 上,其中 \(b\) 的值由点的坐标确定。

不难发现,对于所有的在这一条边上的结点,他们都满足题目中的 \(45^\circ\)度关系,也就是说,如果两个点的 \(x+y\) 相等,那么就可以从下面到左上方的点。

同理,我们可以知道右上方的联通条件是 \(y-x\) 相等。

我们可以花费一些时间离散化和处理每一个点从左上、上、右上三个方向最近到达的点。这部分的时间复杂度为 \(\Theta(n\log _ 2n)\)。

另外,为了方便处理左右方向的情况,我们不妨把纵坐标 \(y\) 相同的点横坐标递增顺序插入到对应的层中,方便后面的运算。这部分的时间复杂度为 \(\Theta(n)\),你可以之前排序的时候以 \(x\) 为第二关键字,这样就不要再次排序了。

递推

不难发现层与层之间的关系比较简单,我们重点考虑层内的做法

假设我目前要从该层的第 \(i\) 个点进入层内,从该层的第 \(j\) 个点出层,那么我们可以分类讨论一下。注意,这里 \(i,j\) 都是层内的点,不是层外的点。

  • \(i=j\),我们必须直接出去,不然待会无法返回。
  • \(i<j\),入点在出点左边,我们可以先从 \(i\) 走到最左边,最后走到出点,这样数量可以最大化。
  • \(i>j\),与上面情况刚好相反,先走到最右边,然后再走到出点。

这里的时间复杂度为 \(\Theta(|S|^2)\to\Theta(n|S|)\),其中 \(|S|\) 为层中的点数,根据数据范围不会超过 \(10^3\)。

求路径

这个没什么好说的,按照之前递推得到的答案数组反过来就是了。

压路机

网络流套路题。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define INF 0X3F3F3F3F
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg bool f=false;
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return f?-res:res;
}

const int MAXN=50000+5;

struct Node{
	int id,x,y,b1,b2;
	inline void Read(reg int i){
		id=i;
		x=read(),y=read();
		b1=y+x;
		b2=y-x;
		return;
	}
	inline bool operator<(const Node& a)const{
		return (y>a.y)||(y==a.y&&x<a.x);
	}
};

int n;
Node a[MAXN];
vector<int> Vx,Vy,Vb1,Vb2;

inline void GetVector(vector<int>& V){
	sort(V.begin(),V.end());
	V.erase(unique(V.begin(),V.end()),V.end());
	return;
}

inline void GetVal(Node &a){
	a.x=lower_bound(Vx.begin(),Vx.end(),a.x)-Vx.begin()+1;
	a.y=lower_bound(Vy.begin(),Vy.end(),a.y)-Vy.begin()+1;
	a.b1=lower_bound(Vb1.begin(),Vb1.end(),a.b1)-Vb1.begin()+1;
	a.b2=lower_bound(Vb2.begin(),Vb2.end(),a.b2)-Vb2.begin()+1;
	return;
}

int T[MAXN],Tb1[MAXN],Tb2[MAXN];
int up[MAXN],lu[MAXN],ru[MAXN];
vector<int> F[MAXN];

inline void Init(void){
	GetVector(Vx),GetVector(Vy),GetVector(Vb1),GetVector(Vb2);
	for(reg int i=1;i<=n;++i)
		GetVal(a[i]);
	sort(a+1,a+n+1);
	for(reg int i=1;i<=n;++i){
		up[i]=T[a[i].x];
		lu[i]=Tb1[a[i].b1];
		ru[i]=Tb2[a[i].b2];
		T[a[i].x]=Tb1[a[i].b1]=Tb2[a[i].b2]=i;
	}
	for(int i=1;i<=n;++i)
		F[a[i].y].push_back(i);
	return;
}

inline void Insert(const Node& a){
	Vx.push_back(a.x);
	Vy.push_back(a.y);
	Vb1.push_back(a.b1);
	Vb2.push_back(a.b2);
	return;
}

inline void Read(void){
	n=read();
	for(reg int i=1;i<=n;++i){
		a[i].Read(i);
		Insert(a[i]);
	}
	a[++n].id=0;
	Insert(a[n]);
	return;
}

namespace Solve1{
	int f[MAXN],Max[MAXN],bup[MAXN];
	int op[MAXN];
	int cnt,path[MAXN];
	int rnk[MAXN];
	inline void Print(reg int k){
		path[++cnt]=a[k].id;
		reg int next=op[k];
		reg int size=F[a[k].y].size();
		if(a[next].x<a[k].x){
			for(reg int i=rnk[k]+1;i<size;++i){
				reg int u=F[a[k].y][i];
				path[++cnt]=a[u].id;
			}
			for(reg int i=rnk[k]-1;i>=rnk[next];--i){
				reg int u=F[a[k].y][i];
				path[++cnt]=a[u].id;
			}
		}
		if(a[next].x>a[k].x){
			for(reg int i=rnk[k]-1;i>=0;--i){
				reg int u=F[a[k].y][i];
				path[++cnt]=a[u].id;
			}
			for(reg int i=rnk[k]+1;i<=rnk[next];++i){
				reg int u=F[a[k].y][i];
				path[++cnt]=a[u].id;
			}
		}
		if(bup[next])
			Print(bup[next]);
		return;
	}
	inline void Solve(void){
		reg int Max_,ptr;
		for(reg int i=Vy.size();i>=1;--i){
			reg int size=F[i].size();
			Max_=ptr=0;
			for(reg int j=0;j<size;++j){
				reg int u=F[i][j];
				rnk[u]=j;
				if(up[u]&&f[up[u]]>Max[u]){
					Max[u]=f[up[u]];
					bup[u]=up[u];
				}
				if(lu[u]&&f[lu[u]]>Max[u]){
					Max[u]=f[lu[u]];
					bup[u]=lu[u];
				}
				if(ru[u]&&f[ru[u]]>Max[u]){
					Max[u]=f[ru[u]];
					bup[u]=ru[u];
				}
				f[u]=Max_,op[u]=ptr;
				if(size-j+Max[u]>Max_)
					Max_=size-j+Max[u],ptr=u;
			}
			Max_=ptr=0;
			for(reg int j=size-1;j>=0;--j){
				reg int u=F[i][j];
				if(Max_>f[u])
					f[u]=Max_,op[u]=ptr;
				if(Max[u]+1>f[u])
					f[u]=Max[u]+1,op[u]=u;
				if(j+1+Max[u]>Max_)
					Max_=j+1+Max[u],ptr=u;
			}
		}
		printf("%d\n",f[n]-1);
		Print(n);
		for(reg int i=2;i<=cnt;++i)
			printf("%d%c",path[i],i==cnt?'\n':' ');
		return;
	}
}

namespace Solve2{
	const int MAXV=MAXN+5;
	const int MAXE=MAXN*10;
	int cnt=1,head[MAXV],to[MAXE],w[MAXE],Next[MAXE];
	inline void Add_Edge(reg int u,reg int v,reg int len){
		Next[++cnt]=head[u];
		to[cnt]=v;
		w[cnt]=len;
		head[u]=cnt;
		return;
	}
	inline void Add_Tube(reg int u,reg int v,reg int len){
		Add_Edge(u,v,len);
		Add_Edge(v,u,0);
		return;
	}
	int dep[MAXV];
	queue<int> Q;
	inline bool BFS(int s,reg int t){
		memset(dep,-1,sizeof(dep));
		while(!Q.empty())Q.pop();
		dep[s]=1,Q.push(s);
		while(!Q.empty()){
			reg int u=Q.front();
			Q.pop();
			for(reg int i=head[u];i;i=Next[i]){
				int v=to[i];
				if(dep[v]==-1&&w[i]>0){
					dep[v]=dep[u]+1;
					Q.push(v);
				}
			}
		}
		return dep[t]!=-1;
	}
	int cur[MAXV];
	inline int DFS(reg int u,reg int t,reg int lim){
		if(u==t)
			return lim;
		reg int flow=0;
		for(reg int &i=cur[u];i;i=Next[i]){
			reg int v=to[i];
			if(dep[v]==dep[u]+1&&w[i]>0){
				reg int f=DFS(v,t,min(lim-flow,w[i]));
				if(f){
					flow+=f;
					w[i]-=f;
					w[i^1]+=f;
					if(flow==lim)
						break;
				}
			}
		}
		return flow;
	}
	inline int Dinic(reg int s,reg int t){
		reg int res=0;
		while(BFS(s,t)){
			memcpy(cur,head,sizeof(head));
			res+=DFS(s,t,INF);
		}
		return res;
	}
	bool vis[MAXN];
	int deg[MAXN];
	inline void Add(reg int x,reg int y){
		for(reg int i=head[x];i;i=Next[i])
			if(to[i]==y)
				return;
		vis[y]=true;
		++deg[y],--deg[x];
		Add_Tube(x,y,INF);
		return;
	}
	inline void Calc(reg int y,reg int i){
		using Solve1::f;
		reg int size=F[y].size();
		reg int p=F[y][i];
		for(reg int j=0;j<i;++j){
			reg int u=F[y][j];
			if(up[u]&&f[up[u]]+size-j==f[p])
				Add(u,up[u]);
			if(lu[u]&&f[lu[u]]+size-j==f[p])
				Add(u,lu[u]);
			if(ru[u]&&f[ru[u]]+size-j==f[p])
				Add(u,ru[u]);
		}
		for(reg int j=i+1;j<size;++j){
			reg int u=F[y][j];
			if(up[u]&&f[up[u]]+j+1==f[p])
				Add(u,up[u]);
			if(lu[u]&&f[lu[u]]+j+1==f[p])
				Add(u,lu[u]);
			if(ru[u]&&f[ru[u]]+j+1==f[p])
				Add(u,ru[u]);
		}
		if(up[p]&&f[up[p]]+1==f[p])
			Add(p,up[p]);
		if(lu[p]&&f[lu[p]]+1==f[p])
			Add(p,lu[p]);
		if(ru[p]&&f[ru[p]]+1==f[p])
			Add(p,ru[p]);
		return;
	}
	inline void Build(void){
		vis[n]=true;
		for(reg int i=1;i<=(int)Vy.size();++i)
			for(reg int j=0,size=F[i].size();j<size;++j)
				if(vis[F[i][j]])
					Calc(i,j);
		return;
	}
	inline void Solve(void){
		Build();
		reg int s=n+1,t=n+2;
		reg int ans=0;
		for(reg int i=1;i<=n;++i)
			if(deg[i]>0){
				Add_Tube(s,i,deg[i]);
				ans+=deg[i];
			}
			else
				Add_Tube(i,t,-deg[i]);
		ans-=Dinic(s,t);
		printf("%d\n",ans);
		return;
	}
}

int main(void){
	Read();
	Init();
	Solve1::Solve();
	Solve2::Solve();
	return 0;
}

相关题目