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)。
HINT
Source
第一二问DP,记录前驱
为了第三问,倒着DP一次
第三问建图跑最小流
然后就没了
码农题,调了N天,两个错误
第一,dinic里面x==T写成x==f
第二,倒着DP里面-l写成-pos
我真是菜
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50010;
const int INF = 1e9;
struct Point { int x, y, id; bool operator < ( const Point &b ) const { return y < b.y || ( y == b.y && x < b.x ); } }p[MAXN];
int f[MAXN], g[MAXN], pre[MAXN], last[MAXN], mx[MAXN], n, ans, st[MAXN], top;
inline int Print()
{
for( int i = ans ; i ; i = last[ i ] )
{
if( !pre[ i ] )
st[ ++top ] = i;
else
{
int x = i, y = pre[ i ];
if( y < x )
{
while( x > y ) st[ ++top ] = x, x--;
while( x && p[ x ].y == p[ y ].y ) x--; x++;
while( x <= y ) st[ ++top ] = x++;
}
else
{
while( x < y ) st[ ++top ] = x, x++;
while( x <= n && p[ x ].y == p[ y ].y ) x++; x--;
while( x >= y ) st[ ++top ] = x--;
}
i = pre[ i ];
}
}
while( top ) printf( "%d", p[ st[ top-- ] ].id ), putchar( !top ? '\n' : ' ' );
}
inline void Dp()
{
map < int, int > mp1, mp2, mp3;
for( int i = 1 ; i <= n ; i++ ) f[ i ] = -INF;
mp1[ 0 ] = mp2[ 0 ] = mp3[ 0 ] = 0;
for( int l = 1, r, pos ; l <= n ; l = r + 1 )
{
r = l; while( r < n && p[ r + 1 ].y == p[ l ].y ) r++;
for( int i = l ; i <= r ; i++ )
{
if( mp1.find( p[ i ].x + p[ i ].y ) != mp1.end() )
{
pos = mp1[ p[ i ].x + p[ i ].y ];
if( f[ i ] < f[ pos ] + 1 ) f[ i ] = f[ pos ] + 1, last[ i ] = pos;
}
mp1[ p[ i ].x + p[ i ].y ] = i;
if( mp2.find( p[ i ].x - p[ i ].y ) != mp2.end() )
{
pos = mp2[ p[ i ].x - p[ i ].y ];
if( f[ i ] < f[ pos ] + 1 ) f[ i ] = f[ pos ] + 1, last[ i ] = pos;
}
mp2[ p[ i ].x - p[ i ].y ] = i;
if( mp3.find( p[ i ].x ) != mp3.end() )
{
pos = mp3[ p[ i ].x ];
if( f[ i ] < f[ pos ] + 1 ) f[ i ] = f[ pos ] + 1, last[ i ] = pos;
}
mp3[ p[ i ].x ] = i;
}
for( int i = l ; i <= r ; i++ ) mx[ i ] = f[ i ];
pos = l;
for( int i = l + 1 ; i <= r ; i++ )
{
if( f[ pos ] < f[ i - 1 ] ) pos = i - 1;
if( mx[ i ] < f[ pos ] + i - l ) mx[ i ] = f[ pos ] + i - l, pre[ i ] = pos;
}
pos = r;
for( int i = r - 1 ; i >= l ; i-- )
{
if( f[ pos ] < f[ i + 1 ] ) pos = i + 1;
if( mx[ i ] < f[ pos ] + r - i ) mx[ i ] = f[ pos ] + r - i, pre[ i ] = pos;
}
for( int i = l ; i <= r ; i++ )
{
f[ i ] = max( f[ i ], mx[ i ] );
if( f[ ans ] < f[ i ] ) ans = i;
}
}
printf( "%d\n", f[ ans ] );
Print();
}
inline void Dp2()
{
map < int, int > mp1, mp2, mp3;
for( int i = 1 ; i <= n ; i++ ) g[ i ] = ( f[ i ] == f[ ans ] ) ? 1 : -INF;
for( int r = n, l, pos ; r >= 0 ; r = l - 1 )
{
l = r; while( l && p[ l - 1 ].y == p[ r ].y ) l--;
for( int i = l ; i <= r ; i++ )
{
if( mp1.find( p[ i ].x + p[ i ].y ) != mp1.end() )
{
pos = mp1[ p[ i ].x + p[ i ].y ];
if( g[ i ] < g[ pos ] + 1 ) g[ i ] = g[ pos ] + 1;
}
mp1[ p[ i ].x + p[ i ].y ] = i;
if( mp2.find( p[ i ].x - p[ i ].y ) != mp2.end() )
{
pos = mp2[ p[ i ].x - p[ i ].y ];
if( g[ i ] < g[ pos ] + 1 ) g[ i ] = g[ pos ] + 1;
}
mp2[ p[ i ].x - p[ i ].y ] = i;
if( mp3.find( p[ i ].x ) != mp3.end() )
{
pos = mp3[ p[ i ].x ];
if( g[ i ] < g[ pos ] + 1 ) g[ i ] = g[ pos ] + 1;
}
mp3[ p[ i ].x ] = i;
}
for( int i = l ; i <= r ; i++ ) mx[ i ] = g[ i ];
pos = l;
for( int i = l + 1 ; i <= r ; i++ )
{
if( g[ pos ] + r - pos < g[ i - 1 ] + r - i + 1 ) pos = i - 1;
if( mx[ i ] < g[ pos ] + r - pos ) mx[ i ] = g[ pos ] + r - pos;
}
pos = r;
for( int i = r - 1 ; i >= l ; i-- )
{
if( g[ pos ] + pos - l < g[ i + 1 ] + i + 1 - l ) pos = i + 1;
if( mx[ i ] < g[ pos ] + pos - l ) mx[ i ] = g[ pos ] + pos - l;
}
for( int i = l ; i <= r ; i++ )
g[ i ] = max( g[ i ], mx[ i ] );
}
}
struct edge { int to, nxt, flow; }e[1000010];
int head[MAXN], cnt = 1, q[MAXN], dis[MAXN], ql, qr, cur[MAXN], S, T, s, t, d[MAXN];
inline void Add(int x, int y, int w) { e[ ++cnt ] = { y, head[ x ], w }; head[ x ] = cnt; }
inline void Addedge(int x, int y, int w) { Add( x, y, w ); Add( y, x, 0 ); }
inline bool Bfs()
{
for( int i = 0 ; i <= T ; i++ ) dis[ i ] = 0;
ql = 0; qr = 1; dis[ q[ qr ] = S ] = 1;
while( ql < qr )
{
int x = q[ ++ql ];
for( int i = head[ x ] ; i ; i = e[ i ].nxt )
if( e[ i ].flow && !dis[ e[ i ].to ] ) dis[ q[ ++qr ] = e[ i ].to ] = dis[ x ] + 1;
}
return dis[ T ];
}
inline int Dfs(int x, int f)
{
if( x == T ) return f;
int ret = 0;
for( int &i = cur[ x ] ; i ; i = e[ i ].nxt )
if( e[ i ].flow && dis[ e[ i ].to ] == dis[ x ] + 1 )
{
int d = Dfs( e[ i ].to, min( f - ret, e[ i ].flow ) );
e[ i ].flow -= d; e[ i ^ 1 ].flow += d; ret += d;
if( ret == f ) return ret;
}
if( !ret ) dis[ x ] = -1;
return ret;
}
inline int Dinic()
{
int ret = 0;
while( Bfs() ) { for( int i = 0 ; i <= T ; i++ ) cur[ i ] = head[ i ]; ret += Dfs( S, INF ); }
return ret;
}
inline void Build()
{
map < int, int > mp1, mp2, mp3;
for( int i = n, pos ; i >= 0 ; i-- )
{
if( mp1.find( p[ i ].x + p[ i ].y ) != mp1.end() )
{
pos = mp1[ p[ i ].x + p[ i ].y ];
if( f[ i ] + g[ pos ] == f[ ans ] ) Addedge( i, pos, INF ), d[ i ]--, d[ pos ]++;
}
mp1[ p[ i ].x + p[ i ].y ] = i;
if( mp2.find( p[ i ].x - p[ i ].y ) != mp2.end() )
{
pos = mp2[ p[ i ].x - p[ i ].y ];
if( f[ i ] + g[ pos ] == f[ ans ] ) Addedge( i, pos, INF ), d[ i ]--, d[ pos ]++;
}
mp2[ p[ i ].x - p[ i ].y ] = i;
if( mp3.find( p[ i ].x ) != mp3.end() )
{
pos = mp3[ p[ i ].x ];
if( f[ i ] + g[ pos ] == f[ ans ] ) Addedge( i, pos, INF ), d[ i ]--, d[ pos ]++;
}
mp3[ p[ i ].x ] = i;
}
for( int i = 0 ; i <= n ; i++ ) Addedge( s, i, INF ), Addedge( i, t, INF );
for( int i = 0 ; i <= n ; i++ )
if( d[ i ] > 0 ) Addedge( S, i, d[ i ] );
else if( d[ i ] < 0 ) Addedge( i, T, -d[ i ] );
}
inline void BFS()
{
memset( dis, 0, sizeof dis );
ql = 0; qr = 1; dis[ q[ qr ] = S ] = 1;
while( ql ^ qr )
{
int x = q[ ++ql ];
for( int i = head[ x ] ; i ; i = e[ i ].nxt )
{
printf( "%d %d %d\n", x, e[ i ].to, e[ i ].flow );
if( !dis[ e[ i ].to ] ) dis[ q[ ++qr ] = e[ i ].to ] = dis[ x ] + 1;
}
}
}
int main()
{
scanf( "%d", &n );
s = n + 1 , t = n + 2, S = n + 3, T = n + 4;
for( int i = 1 ; i <= n ; i++ ) scanf( "%d%d", &p[ i ].x, &p[ i ].y ), p[ i ].id = i;
sort( p + 1, p + n + 1 );
Dp();
Dp2();
Build();
Dinic();
Addedge( t, s, INF );
Dinic();
//printf( "BFS:\n" );
//BFS();
printf( "%d\n", e[ cnt ].flow );
return 0;
}
