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

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

题目链接：Luogu P2304、LibreOJ 2134、BZOJ 4200、UOJ 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 首先选择任意一个满足以下条件的方向：

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

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

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

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

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

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

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

数据范围

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

对于所有数据，\(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;
}

友情链接

近期评论

题目

题目描述

数据范围

时空限制

题解

思路

建图

递推

求路径

压路机

代码

相关题目

You may also like...

发表评论取消回复

题目

题目描述

数据范围

时空限制

题解

思路

建图

递推

求路径

压路机

代码

相关题目

You may also like...

「题解」「JLOI2014」镜面通道 mirror

「题解」「SDOI2017」新生舞会 ball

「题解」「CF1325F」Ehab’s Last Theorem

发表评论 取消回复

发表评论取消回复