【BZOJ2839】[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

-1 1

1 1

-2 2

0 8

0 9

0 10

Sample Output

2 1 3

explanation

最优路线 2 条可许愿 3 次：(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)和 (0,0)→(0,8)→(0,9)→(0,10)。

题解：超级码农题，我一共进行了下面5个操作：

1.预处理出每个点在5个方向上最近的点。

2.正着进行第一次DP，求出f[i]表示从原点到i的最长路径长度，顺便记录个路径。

3.递归输出路径。

4.反着再来一次DP，求出哪些路径在最优路线上。

5.求最小流。

细节有点多，自己的做法也有点麻烦，一个一个说吧~

1.排个序，开3个map搞定。

2.向上转移倒是容易，但是左右转移就有点麻烦了。用f0表示由向上转移得到的DP值，f1表示由左右转移或向上转移得到的DP值。我们先从左往右扫一遍，用f0的前缀最大值+i左边的点的个数来更新i的f1。顺便记录一下i的f0和f1都是从谁转移过来的。再同样的从右往左扫一遍。

3.递归输出即可。如果有左右转移，要把左（右）边所有点都输出，具体顺序好像无所谓。

4.最恶心的一步！因为要求最小流，所以我们要把所有在最优路线上的点都找出来，一个可行的方法就是反过来DP一遍，用g[i]表示从任意一个最优的结束点到i的最长路径长度。如果f[i]+g[j]=最长路径长度，那么i-j这条边在最优路线上。

但是我的方法更麻烦。给每个节点都打一个vis标记，起初最优结束点的vis=2。如果vis&1说明它可以向下传递标记，如果vis&2说明它可以左右传递标记。如果标记能沿着一条路径传递，则说明这条路径在最优路线上。具体地，vis&2的标记在左右传递后vis变成1，vis&1的标记在向下传递后vis变成2，如果一个点的f0=f1，且vis=1或2，那么vis=3。感觉正常人应该不懂我在说什么~

5.最小流。这里学到了一种求最小流的新方法：先不练T到S的那条边，跑从SS到TT的最大流，设流量为x1，再连从T到S，容量inf的边，跑从SS到TT的最大流，设增加的流量为x2，如果第二次满流则说明有解。但是本题一定是能满流的，所以不需要跑第二次，甚至不需要S和T两点，直接用满流-x1就行了。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           using namespace std;const int maxn=50010;const int inf=1<<30;//0左1右2上3左上4右上typedef long long ll;struct tree{ int x,y,np[5],vis,org,ls,rs,p1,p2;}p[maxn];int n,cnt,S,T,flag,top;ll tot,ans;map
           
             m2,m3,m4;int f0[maxn],f1[maxn],mn[maxn],st[maxn],d[maxn],p1[maxn],p2[maxn];int to[1000000],next[1000000],val[1000000],head[maxn];queue
            
              q;bool cmpy(tree a,tree b){ return (a.y==b.y)?(a.x
             
              
               f1[j]) f1[j]=f0[mx]+p[j].ls,p1[j]=mx; if(f0[j]>f0[mx]) mx=j; } if(!p[i].np[1]) { for(mx=0,j=i;j;j=p[j].np[0]) { if(f0[mx]+p[j].rs>f1[j]) f1[j]=f0[mx]+p[j].rs,p1[j]=mx; if(f0[j]>f0[mx]) mx=j; } for(j=i;j;j=p[j].np[0]) for(k=2;k<=4;k++) if(p[j].np[k]) if(f0[p[j].np[k]]
               
                f1[mf]) mf=i; printf("%d\n",f1[mf]); print(mf); printf("\n"); for(i=n;i>=1;i--) { if(!p[i].np[1]) { for(top=0,mx=-inf,j=i;j;j=p[j].np[0]) { if(f1[j]==f1[mf]) p[j].vis=2; for(k=2;k<=4;k++) if(p[j].np[k]) { if((p[p[j].np[k]].vis&1)&&f0[p[j].np[k]]==f1[j]+1) { mn[p[j].np[k]]++,mn[j]--,add(j,p[j].np[k],inf),p[j].vis|=2; } } if(p[j].vis&&f1[j]==f0[j]) p[j].vis|=1; if((p[j].vis&2)&&mx+p[j].rs==f1[j]) { while(top) p[st[top--]].vis|=1; } if(f0[j]>mx) mx=f0[j],top=0; if(!(p[j].vis&1)&&f0[j]==mx) st[++top]=j; } } if(!p[i].np[0]) { for(top=0,mx=-inf,j=i;j;j=p[j].np[1]) { if((p[j].vis&2)&&mx+p[j].ls==f1[j]) { while(top) p[st[top--]].vis|=1; } if(f0[j]>mx) mx=f0[j],top=0; if(!(p[j].vis&1)&&f0[j]==mx) st[++top]=j; } } }}int rd(){ int ret=0,f=1; char gc=getchar(); while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();} while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar(); return ret*f;}int dfs(int x,int mf){ if(x==T) return mf; int k,temp=mf,i; for(i=head[x];i!=-1;i=next[i]) { if(d[to[i]]==d[x]+1&&val[i]) { k=dfs(to[i],min(temp,val[i])); if(!k) d[to[i]]=0; val[i]-=k,val[i^1]+=k,temp-=k; if(!temp) break; } } return mf-temp;}int bfs(){ memset(d,0,sizeof(d)); while(!q.empty()) q.pop(); int i,u; q.push(S),d[S]=1; while(!q.empty()) { u=q.front(),q.pop(); for(i=head[u];i!=-1;i=next[i]) { if(!d[to[i]]&&val[i]) { d[to[i]]=d[u]+1; if(to[i]==T) return 1; q.push(to[i]); } } } return 0;}int main(){ n=rd(); int i; memset(head,-1,sizeof(head)); for(i=1;i<=n;i++) p[i].x=rd(),p[i].y=rd(),p[i].org=i; n++; getnp(),DP(); S=n+1,T=n+2; for(i=1;i<=n;i++) { if(mn[i]>0) tot+=mn[i],add(S,i,mn[i]); if(mn[i]<0) add(i,T,-mn[i]); } while(bfs()) ans+=dfs(S,inf); printf("%lld",tot-ans); return 0;}

转载于:https://www.cnblogs.com/CQzhangyu/p/7124570.html

你可能感兴趣的文章