一开始想DP做法。。发现不会QAQ
暴力费用流挺好想的。。就是拆点限制经过次数，然后每个点的出点往能到达的点的入点连边。。跑个最大费用最大流。
但显然边数能达到n^2。。显而易见的优化就是，如果存在路径点a->b->c,那么a就没必要连往c了。（虽然优化完极限情况下边数也差不多是n^2了。。。）
但是有可能出现借道的情况。就从入点往出点连一条流量1，费用0的边。（不会被借道两次）
有一个神坑。。。这题用spfa跑最长路的时候，队列数组要开到n^2。。。。。因为这个原因卡了一个晚上
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define ll long long 7 using namespace std; 8 const int maxn=4023,inf=1002333333; 9 struct poi{int x,y;}a[maxn]; 10 struct zs{int pre;short too,flow,dis;}e[4233333];int tot,last[maxn]; 11 short dl[4233333]; 12 int dis[maxn]; 13 bool u[maxn],ins[maxn]; 14 int i,j,k,n,m,s,t,ss; 15 int ans; 16 17 int ra;char rx; 18 inline int read(){ 19 rx=getchar(),ra=0; 20 while(rx<'0'||rx>'9')rx=getchar(); 21 while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,rx=getchar();return ra; 22 } 23 24 bool spfa(){ 25 memset(dis,255,(t+1)<<2),dis[ss]=0,dl[1]=ss,u[ss]=1; 26 int l=0,r=1,i,now; 27 while(l<r&&!dis[ss]) 28 for(i=last[now=dl[++l]],u[now]=0;i;i=e[i].pre)if(e[i].flow&&dis[e[i].too]<dis[now]+e[i].dis){ 29 dis[e[i].too]=dis[now]+e[i].dis; 30 if(!u[e[i].too])u[e[i].too]=1,dl[++r]=e[i].too; 31 } 32 return dis[t]>-1; 33 } 34 inline int min(int a,int b){return a<b?a:b;} 35 int dfs(int x,int mx){ 36 if(x==t)return mx; 37 int used=0,i,w;ins[x]=1; 38 for(i=last[x];i;i=e[i].pre)if(e[i].flow&&dis[e[i].too]==dis[x]+e[i].dis&&!ins[e[i].too]) 39 if((w=dfs(e[i].too,min(mx-used,(int)e[i].flow)))){ 40 e[i].flow-=w,e[i^1].flow+=w,ans+=w*e[i].dis,used+=w; 41 if(used==mx){ins[x]=0;return mx;} 42 } 43 dis[x]=-1,ins[x]=0;return used; 44 } 45 46 inline void insert(int a,int b,int c,int d){ 47 e[++tot].too=b,e[tot].flow=c,e[tot].dis= d,e[tot].pre=last[a],last[a]=tot, 48 e[++tot].too=a,e[tot].flow=0,e[tot].dis=-d,e[tot].pre=last[b],last[b]=tot; 49 } 50 bool cmp(poi a,poi b){return a.x<b.x||(a.x==b.x&&a.y<b.y);} 51 int main(){ 52 n=read(); 53 for(i=1;i<=n;i++) 54 a[i].x=read(),a[i].y=read(); 55 sort(a+1,a+1+n,cmp); 56 ss=0,s=n<<1|1,t=s+1,tot=1; 57 insert(ss,s,2,0); 58 for(i=1;i<=n;i++){ 59 insert(i,i+n,1,0),insert(i,i+n,1,1),insert(s,i,1,0),insert(i+n,t,1,0); 60 int mn=inf; 61 for(j=i+1;j<=n;j++) 62 if(a[j].y<mn&&a[j].y>=a[i].y)mn=a[j].y,insert(i+n,j,2,0); 63 } 64 while(spfa())dfs(ss,inf); 65 printf("%d ",ans); 66 }