uoj132&&bzoj4200 【NOI2015】小园丁与老司机

uoj132&&bzoj4200 【NOI2015】小园丁与老司机

​​ Description 小园丁 Mr. S 负责看管一片田野，田野可以看作一个二维平面。田野上有 nn 棵许愿树，编号 1,2,3,…,n1,2,3,…,n，每棵树可以看作平面上的一个点，其中第 ii 棵树 （1≤i≤n1≤i≤n） 位于坐标 (xi,yi)(xi,yi)。任意两棵树的坐标均不相同。 老司机 Mr. P 从原点 (0,0)(0,0) 驾车出发，进行若干轮行动。每一轮，Mr. P 首先选择任意一个满足以下条件的方向： 为左、右、上、左上 45∘45∘ 、右上 45∘45∘ 五个方向之一。 沿此方向前进可以到达一棵他尚未许愿过的树。 完成选择后，Mr. P 沿该方向直线前进，必须到达该方向上距离最近的尚未许愿的树，在树下许愿并继续下一轮行动。如果没有满足条件的方向可供选择，则停止行动。他会采取最优策略，在尽可能多的树下许愿。若最优策略不唯一，可以选择任意一种。 不幸的是，小园丁 Mr. S 发现由于田野土质松软，老司机 Mr. P 的小汽车在每轮行进过程中，都会在田野上留下一条车辙印，一条车辙印可看作以两棵树（或原点和一棵树）为端点的一条线段。 在 Mr. P 之后，还有很多许愿者计划驾车来田野许愿，这些许愿者都会像 Mr. P 一样任选一种最优策略行动。Mr. S 认为非左右方向（即上、左上 45∘45∘ 、右上 45∘45∘ 三个方向）的车辙印很不美观，为了维护田野的形象，他打算租用一些轧路机，在这群许愿者到来之前夯实所有“可能留下非左右方向车辙印”的地面。 “可能留下非左右方向车辙印”的地面应当是田野上的若干条线段，其中每条线段都包含在某一种最优策略的行进路线中。每台轧路机都采取满足以下三个条件的工作模式： 从原点或任意一棵树出发。 只能向上、左上 45∘45∘ 、右上 45∘45∘ 三个方向之一移动，并且只能在树下改变方向或停止。 只能经过“可能留下非左右方向车辙印”的地面，但是同一块地面可以被多台轧路机经过。 现在 Mr. P 和 Mr. S 分别向你提出了一个问题: 请给 Mr .P 指出任意一条最优路线。 请告诉 Mr. S 最少需要租用多少台轧路机。

Input 输入文件的第 1 行包含 1 个正整数 n，表示许愿树的数量。

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

Output 输出文件包括 3 行。 输出文件的第 1 行输出 1 个整数 m，表示 Mr. P 最多能在多少棵树下许愿。 输出文件的第 2 行输出 m 个整数，相邻整数之间用单个空格隔开，表示 Mr. P 应该依次在哪些树下许愿。 输出文件的第 3 行输出 1 个整数，表示 Mr. S 最少需要租用多少台轧路机。

Sample Input 6 -1 1 1 1 -2 2 0 8 0 9 0 10 Sample Output 3 2 1 3 3 explanation

最优路线 2 条可许愿 3 次：(0,0)→(1,1)→(−1,1)→(−2,2)(0,0)→(1,1)→(−1,1)→(−2,2) 或 (0,0)→(0,8)→(0,9)→(0,10)(0,0)→(0,8)→(0,9)→(0,10)。 至少 3 台轧路机，路线是 (0,0)→(1,1)(0,0)→(1,1)，(−1,1)→(−2,2)(−1,1)→(−2,2) 和 (0,0)→(0,8)→(0,9)→(0,10)(0,0)→(0,8)→(0,9)→(0,10)。

之前写过这题但是复杂度不对 在uoj被hack ​​ path用来记录层与层之间的转移 虽然最多只有三个 还是开vector pre用来记录层内的转移 有可能很多需要vector 原来n^2转移限制可以暴力o(n)扫描一遍 用pre1记录之前有多少个可以转移到我这个点的最优值 注意初值给-inf 否则会被hack 其他详细做法看我曾经的blog 虽然这题并不需要判断是否有解 但最小流要求我们如果只是最小流的题目 第一遍跑网络流的时候需要判断是否误解 就把所有正的d加起来看是否和网络流值相同即可

#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=1e5+10;const int inf=0x3f3f3f3f;struct node{ int x,y,s,d,id;}p[N];int n,nn,ls[N],lsx[N],lss[N],lsd[N],bl[N],dp[N],bk[N];vector pre[N],pre1,path[N],ans;bool flag[N];int num=1,h[N],level[N],d[N],s,t,S,T,cur[N];inline bool cmp(const node &a,const node &b){ return a.y==b.y?a.xq;memset(level,0,sizeof(level));level[S]=1;q.push(S); while(!q.empty()){ int x=q.front();q.pop(); for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if(level[y]||!z) continue;level[y]=level[x]+1;if (y==T) return 1;q.push(y); } }return 0;}inline int dfs2(int x,int s){ if (x==T) return s;int ss=s; for (int &i=cur[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if(level[x]+1==level[y]&&z){ int xx=dfs2(y,min(z,s));if (!xx) level[y]=0; s-=xx;data[i].z-=xx;data[i^1].z+=xx;if(!s) return ss; } }return ss-s;}inline void dfs(int x){ if(!x) return;ans.push_back(x); if(pre[x].empty()) {x=path[x][0];dfs(x);return;} int px=pre[x][0]; if(bl[px]bl[x]){ int now=bl[x]+1; while(p[now].id!=px) ans.push_back(p[now].id),++now; now=bl[px]+1; while(p[now+1].y==p[bl[x]].y) ++now; while(p[now].id!=px&&p[now].y==p[bl[x]].y) ans.push_back(p[now].id),--now; }ans.push_back(px);x=path[px][0];dfs(x);}inline void dfs1(int x){ if (!x) return;//{puts("---");return;} if(!path[x].empty()&&dp[path[x][0]]+1==dp[x]){ pre[x].push_back(x); } for (int i=0;idp[id]){ path[id].clear();dp[id]=dp[lsx[x]]+1; path[id].push_back(lsx[x]); }lsx[x]=id; if (dp[lss[s]]+1>dp[id]){ path[id].clear();dp[id]=dp[lss[s]]+1; path[id].push_back(lss[s]); }else if (dp[lss[s]]+1==dp[id]) path[id].push_back(lss[s]);lss[s]=id; if (dp[lsd[d]]+1>dp[id]){ path[id].clear();dp[id]=dp[lsd[d]]+1; path[id].push_back(lsd[d]); }else if (dp[lsd[d]]+1==dp[id]) path[id].push_back(lsd[d]);lsd[d]=id; }int preans=0; for (int i=fr;i<=to;++i){ int id=p[i].id;bk[i]=dp[id]; if (preans&&preans+i-fr>dp[id]){ dp[id]=preans+i-fr;pre[id].clear();pre[id]=pre1; }else{ if (preans&&preans+i-fr==dp[id]) for (int j=0;jpreans) preans=bk[i],pre1.clear(),pre1.push_back(id); }preans=0;pre1.clear(); for (int i=to;i>=fr;--i){ int id=p[i].id; if (preans&&preans+to-i>dp[id]){ dp[id]=preans+to-i;pre[id].clear();pre[id]=pre1; }else{ if (preans&&preans+to-i==dp[id]) for (int j=0;jpreans) preans=bk[i],pre1.clear(),pre1.push_back(id); } fr=owo; } }int ansx=0,pos=0; for (int i=1;i<=n;++i) if (ansx0) insert1(S,i,d[i]); insert1(i,t,inf);insert1(s,i,inf); }ansx=0; while(bfs()) memcpy(cur,h,sizeof(h)),dfs2(S,inf); insert1(t,s,inf); while(bfs()) memcpy(cur,h,sizeof(h)),dfs2(S,inf); printf("%d\n",data[num].z); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。