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\) | ||
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; }
近期评论