小园丁 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 最少需要租用多少台轧路机。

哈哈哈我可能是疯了所以才去做了码农题，然后dp不会最小流写跪哈哈哈

直接看这个吧，心累到懒得讲题解了：

另外开O2的时候普通的最小流也可以通过，不开的时候就会奇妙RE。

（自认码风不错）

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               using namespace std;typedef long long ll;const int INF=1e9;const int N=5e4+5;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}struct point{ int x,y,b1,b2,id;}p[N];int n,b[N],c[N],d[N],e[N],l1,l2,l3,l4;int to[3][N],lft[N],straight[N],rigt[N];int f[N],g[N],flor[N],num[N];vector
               
                ty[N];inline bool cmpx(point a,point b){ return a.x
                
                 b.y;}void LSH(){ sort(b+1,b+l1+1);sort(c+1,c+l2+1); sort(d+1,d+l3+1);sort(e+1,e+l4+1); l1=unique(b+1,b+l1+1)-b-1,l2=unique(c+1,c+l2+1)-c-1; l3=unique(d+1,d+l3+1)-d-1,l4=unique(e+1,e+l4+1)-e-1; for(int i=1;i<=n;i++){ p[i].x=lower_bound(b+1,b+l1+1,p[i].x)-b; p[i].y=lower_bound(c+1,c+l2+1,p[i].y)-c; p[i].b1=lower_bound(d+1,d+l3+1,p[i].b1)-d; p[i].b2=lower_bound(e+1,e+l4+1,p[i].b2)-e; }}void init(){ LSH(); sort(p+1,p+n+1,cmpy); for(int i=1;i<=n;i++){ int id=p[i].id; to[0][id]=lft[p[i].b2]; to[1][id]=straight[p[i].x]; to[2][id]=rigt[p[i].b1]; lft[p[i].b2]=id; straight[p[i].x]=id; rigt[p[i].b1]=id; } sort(p+1,p+n+1,cmpx); for(int i=1;i<=n;i++){ ty[p[i].y].push_back(p[i].id); flor[p[i].id]=p[i].y; num[p[i].id]=ty[p[i].y].size()-1; }}int pre[N],lrs[N];void output(int id){ if(id!=lrs[id]){ int fll=flor[id]; if(num[id]
                 
                  =0;i--)printf("%d ",ty[fll][i]); for(int i=num[id]+1;i<=num[lrs[id]];i++)printf("%d ",ty[fll][i]); }else{ int sz=ty[fll].size(); for(int i=num[id]+1;i
                  
                   =num[lrs[id]];i--)printf("%d ",ty[fll][i]); } } id=lrs[id]; if(pre[id]){ printf("%d ",pre[id]); output(pre[id]); }}void work1(){ init(); for(int i=l2;i>=1;i--){ int maxn=0,id=0,sz=ty[i].size(); for(int j=0;j
                   
                    g[I]+1)f[I]=maxn,lrs[I]=id; else f[I]=g[I]+1,lrs[I]=I; if(sz-j+g[I]>maxn)maxn=sz-j+g[I],id=I; } maxn=id=0; for(int j=sz-1;j>=0;j--){ //处理向左再右走 int I=ty[i][j]; if(maxn>f[I])f[I]=maxn,lrs[I]=id; if(g[I]+j+1>maxn)maxn=g[I]+j+1,id=I; } } printf("%d\n",f[n]-1);output(n);puts("");}struct node{ int to,nxt,w;}edge[N*10];int cnt,head[N],S,T,du[N];int cur[N],lev[N],dui[N];bool ok[N];inline void adde(int u,int v,int w){ edge[++cnt].to=v;edge[cnt].w=w;edge[cnt].nxt=head[u];head[u]=cnt; edge[++cnt].to=u;edge[cnt].w=0;edge[cnt].nxt=head[v];head[v]=cnt;}inline void add(int u,int v){ for(int i=head[u];i!=-1;i=edge[i].nxt) if(edge[i].to==v)return; du[u]--;du[v]++;adde(u,v,INF-1);}bool bfs(int m){ int r; for(int i=1;i<=m;i++){ cur[i]=head[i];lev[i]=-1; } dui[r=0]=S;lev[S]=0; for(int i=0;i<=r;i++){ int u=dui[i]; for(int j=head[u];j!=-1;j=edge[j].nxt){ int v=edge[j].to,w=edge[j].w; if(lev[v]==-1&&w){ lev[v]=lev[u]+1; dui[++r]=v; if(v==T)return 1; } } } return 0;}int dinic(int u,int flow,int m){ if(u==m)return flow; int res=0,delta; for(int &i=cur[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; if(lev[v]>lev[u]&&edge[i].w){ delta=dinic(v,min(flow,edge[i].w),m); if(delta){ edge[i].w-=delta; edge[i^1].w+=delta; res+=delta; if(res==flow)break; } } } if(res!=flow)lev[u]=-1; return res;}void build(){ ok[n]=1; for(int i=1;i<=l2;i++){ int sz=ty[i].size(); for(int j=0;j
                    
                     0)adde(S,i,du[i]),ans+=du[i]; else if(du[i]<0)adde(i,T,-du[i]); } while(bfs(T))ans-=dinic(S,INF,T); printf("%d\n",ans);}int main(){ n=read(); for(int i=1;i<=n;i++){ p[i].x=b[++l1]=read(); p[i].y=c[++l2]=read(); p[i].b1=d[++l3]=p[i].y-p[i].x; p[i].b2=e[++l4]=p[i].y+p[i].x; p[i].id=i; } p[++n].x=b[++l1]=0; p[n].y=c[++l2]=0; p[n].b1=d[++l3]=0; p[n].b2=e[++l4]=0; p[n].id=n; work1();work2(); return 0;}
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

+++++++++++++++++++++++++++++++++++++++++++

 +本文作者：luyouqi233。 　　　　　　　　　　　　　　+

 +欢迎访问我的博客：+

+++++++++++++++++++++++++++++++++++++++++++