https://blog.csdn.net/litble/article/details/80463466
https://www.cnblogs.com/cjyyb/p/9288367.html
一上午就弄这道题 犯了很多错误 比如排序排错 没更新啥的。。
大概是把(y)从大到小dp (dp_i)表示从(i)向上或斜向上走最多多少点
(g_i)表示假如(i)是这一层第一个到达的点从(i)开始走最多多少点 可以在这一层走一遍
同一层内从(i)开始到(j)离开该层的话会先绕到该层端点再到(j)
当然也可以直接从(i)离开该层
第二问需要上下界最小流
litble给出了一个神奇的针对这个图的上下界最小流方法 太神了
我实现的好麻烦。。
#include<bits/stdc++.h>
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);i<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);i>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
#define mem(a) memset((a),0,sizeof (a))
#define O(x) cerr<<#x<<':'<<x<<endl
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
void wr(int x){
if(x<0)putchar('-'),x=-x;
if(x>=10)wr(x/10);
putchar('0'+x%10);
}
const int MAXN=50020,inf=1e9+1e7;
struct poi{
int x,y,id;
}p[MAXN],sta[MAXN];
inline bool cmp1(poi a,poi b){
if(a.x!=b.x)return a.x<b.x;
return a.y<b.y;
}
inline bool cmp2(poi a,poi b){
if(a.y!=b.y)return a.y>b.y;
return a.x<b.x;
}
inline bool cmp3(poi a,poi b){
if(a.y!=b.y)return a.y<b.y;
return a.x<b.x;
}
map<int,int>mp;
int n,frm[MAXN],g[MAXN],dp[MAXN],to[MAXN][5],top,pos[MAXN],grm[MAXN],gp[MAXN];
void output(int x){
if(!x)return;
if(p[gp[grm[x]]].y!=p[gp[x]].y){printf("%d ",x),output(grm[x]);return;}
top=0;int l=gp[x],r=gp[x],p1=-1,p2=-1;
while(l>1&&p[l-1].y==p[gp[x]].y)--l;while(r+1<=n&&p[r+1].y==p[gp[x]].y)++r;
fp(i,l,r)sta[++top]=p[i];
fp(i,1,top)if(sta[i].id==x)p1=i;
fp(i,1,top)if(sta[i].id==grm[x])p2=i;
assert(p1!=-1);assert(p2!=-1);
if(p2>p1){
fd(i,p1,1)printf("%d ",sta[i].id);
fp(i,p1+1,p2)printf("%d ",sta[i].id);
}
else{
fp(i,p1,top)printf("%d ",sta[i].id);
fd(i,p1-1,p2)printf("%d ",sta[i].id);
}
output(frm[grm[x]]);
}
inline void solve1(){
sort(p+1,p+1+n,cmp1);
fp(i,1,n-1)if(p[i].x==p[i+1].x)to[p[i].id][2]=p[i+1].id;
fp(i,1,n)if(p[i].x==0){to[0][2]=p[i].id;break;}
mp.clear();
fp(i,1,n){
int t=p[i].x+p[i].y;
if(mp[t])to[p[i].id][3]=mp[t];mp[t]=p[i].id;
if(!t)to[0][3]=p[i].id;
}
mp.clear();
fd(i,n,1){
int t=p[i].x-p[i].y;
if(mp[t])to[p[i].id][4]=mp[t];mp[t]=p[i].id;
if(!t)to[0][4]=p[i].id;
}
sort(p+1,p+1+n,cmp2);
for(int l=1,r;l<=n;l=r+1){
r=l;while(r<n&&p[r+1].y==p[l].y)++r;top=0;
fp(i,l,r)sta[++top]=p[i];
fp(i,1,top)fp(j,2,4){
int t=sta[i].id;
if(dp[t]<g[to[t][j]]+1)dp[t]=g[to[t][j]]+1,frm[t]=to[t][j];
}
fp(i,1,top)g[sta[i].id]=dp[sta[i].id],grm[sta[i].id]=frm[sta[i].id];
int p=1;
fp(i,2,top){
int t=dp[sta[p].id]+top-p;
if(t>g[sta[i].id])g[sta[i].id]=t,grm[sta[i].id]=sta[p].id;
if(dp[sta[i].id]+top-i>t)p=i;
}
p=top;
fd(i,top-1,1){
int t=dp[sta[p].id]+p-1;
if(t>g[sta[i].id])g[sta[i].id]=t,grm[sta[i].id]=sta[p].id;
if(t<dp[sta[i].id]+i-1)p=i;
}
}
fp(j,2,4)
if(dp[0]<g[to[0][j]])dp[0]=g[to[0][j]],frm[0]=grm[0]=to[0][j];
printf("%d
",g[0]=dp[0]);
fp(i,1,n)gp[p[i].id]=i;
output(grm[0]);puts("");
}
struct tEdge{
int v,next,w;
}e[MAXN<<5];
int front[MAXN],tcnt=1,dep[MAXN],deg[MAXN],S,T,SS,TT,ans,head[MAXN];
bool visg[MAXN],visf[MAXN];
inline void adde(int u,int v,int w){
e[++tcnt]={v,front[u],w};front[u]=tcnt;
e[++tcnt]={u,front[v],0};front[v]=tcnt;
}
inline void add(int u,int v){
++deg[v];--deg[u];adde(u,v,inf);
}
int q[MAXN],cnt;
inline bool bfs(){
q[cnt=1]=SS;mem(dep);dep[SS]=1;
fp(tt,1,cnt){
int u=q[tt];
fe(i,u){
int v=e[i].v,w=e[i].w;if(!w||dep[v])continue;
dep[v]=dep[u]+1;q[++cnt]=v;
}
}
return !!dep[TT];
}
int dfs(int u,int flow){
if(u==TT)return flow;
int used=0;
for(int &i=head[u];i;i=e[i].next){
int v=e[i].v,w=e[i].w;if(!w||dep[v]!=dep[u]+1)continue;int tmp;
if(tmp=dfs(v,min(flow-used,e[i].w))){
e[i].w-=tmp;e[i^1].w+=tmp;used+=tmp;
}
if(used==flow)return used;
}
dep[u]=0;return used;
}
inline void solve2(){
sort(p+1,p+1+n,cmp3);
fp(j,2,4)
if(to[0][j]&&dp[0]==g[to[0][j]])visg[to[0][j]]=1,add(0,to[0][j]);visg[0]=visf[0]=1;
for(int l=1,r;l<=n;l=r+1){
r=l;while(r<n&&p[r+1].y==p[l].y)++r;top=0;
fp(i,l,r)sta[++top]=p[i];
fp(i,1,top)if(visg[sta[i].id]&&dp[sta[i].id]==g[sta[i].id])visf[sta[i].id]=1;
vector<int>buc;buc.clear();
int t=dp[sta[1].id]+top-1;buc.push_back(sta[1].id);
fp(i,2,top){
if(visg[sta[i].id]&&g[sta[i].id]==t){
for(int t:buc)visf[t]=1;buc.clear();
}
int x=dp[sta[i].id]+top-i;
if(x>t)t=x,buc.clear(),buc.push_back(sta[i].id);
else if(x==t)buc.push_back(sta[i].id);
}
buc.clear();
buc.push_back(sta[top].id);t=dp[sta[top].id]+top-1;
fd(i,top-1,1){
if(visg[sta[i].id]&&g[sta[i].id]==t){
for(int t:buc)visf[t]=1;buc.clear();
}
int x=dp[sta[i].id]+i-1;
if(x>t)t=x,buc.clear(),buc.push_back(sta[i].id);
else if(x==t)buc.push_back(sta[i].id);
}
fp(i,1,top)if(visf[sta[i].id]){
int t=sta[i].id;
fp(j,2,4){
if(g[to[t][j]]+1==dp[t])add(t,to[t][j]),visg[to[t][j]]=1;
}
}
}
S=n+1;T=n+2;SS=n+3;TT=n+4;
fp(i,0,n)if(visg[i]||visf[i]){
adde(S,i,inf);adde(i,T,inf);
}
fp(i,0,n)if(deg[i]){
if(deg[i]>0)adde(SS,i,deg[i]);
else adde(i,TT,-deg[i]);
}
while(bfs()){
memcpy(head,front,sizeof head);dfs(SS,inf);
}
adde(T,S,inf);
while(bfs()){
memcpy(head,front,sizeof head);ans+=dfs(SS,inf);
}
printf("%d
",ans);
}
main(){
n=read();
fp(i,1,n)p[i].x=read(),p[i].y=read(),p[i].id=i;
solve1();solve2();
return 0;
}