一开始我觉得这不是一个弱弱的费用流吗？

每个豆豆拆点，入点出点随便连连

由于肯定是DAG图，边权为正的最大费用肯定能增广出来

于是我们只要跑总流量为2的最大费用最大流不就行了吗

但是

这样会TLE，因为会出现稠密图，spfa跑稠密图太慢

既然这样，能不能换一个找增广路的方法呢？

最大路径更快的方法就是DAG图的拓扑排序+dp

但好像无法处理反向弧导致带来的环啊

那既然这样，反正总流量很小，

我们可以用DAG解决最大路径特有的dp找第一条增广路（因为这时候是肯定的DAG），跑出一个较大费用

然后再用spfa增广呢？这样就大大减小了时间复杂度

这就是AC方法

注意这道题空间卡的较紧，能开integer不要开longint

实现起来要小心

1 const mo=4010;  2 type node=record  3        next:longint;  4        point,flow,cost:integer;  5      end;  6   7 var edge:array[0..4100000] of node;  8     v:array[0..4010] of boolean;  9     d,rd,pre,pref:array[0..4010] of integer; 10     q:array[0..4010] of integer; 11     p,x,y,cur:array[0..4010] of longint; 12     len:longint; 13     max,s,t,i,j,n,m,be:integer; 14  15 procedure add(x,y,f,c:integer); 16   begin 17     edge[len].point:=y; 18     edge[len].flow:=f; 19     edge[len].cost:=c; 20     edge[len].next:=p[x]; 21     p[x]:=len; 22   end; 23  24 procedure preflow; 25   var x,y,f,r,i,j:longint; 26   begin 27     r:=1; 28     f:=1; 29     q[1]:=s; 30     while f<=r do  //拓扑排序 31     begin 32       x:=q[f]; 33       i:=p[x]; 34       while i<>-1 do 35       begin 36         y:=edge[i].point; 37         dec(rd[y]); 38         if (rd[y]=0) then 39         begin 40           inc(r); 41           q[r]:=y; 42         end; 43         i:=edge[i].next; 44       end; 45       inc(f); 46     end; 47     fillchar(d,sizeof(d),255); 48     d[s]:=0; 49     for j:=1 to r do //DAG图根据拓扑的顺序dp解决最大路径 50     begin 51       x:=q[j]; 52       i:=p[x]; 53       while i<>-1 do 54       begin 55         y:=edge[i].point; 56         if d[y]
      
       d[max] then max:=y; 62         end; 63         i:=edge[i].next; 64       end; 65     end; 66   end; 67  68 procedure change;   //建立预处理后的网络继续增广 69   var i,j,e,w:longint; 70   begin 71     for i:=1 to n do 72       pref[i]:=1; 73     i:=max; 74     while i<>s do   //相当于找到第一条增广路然后弄一弄反向弧什么的 75     begin 76       pref[i]:=0; 77       j:=cur[i]; 78       dec(edge[j].flow); 79       if pre[i]=s then w:=i; 80       i:=pre[i]; 81     end; 82     len:=-1; 83     for i:=1 to n do 84       for j:=1 to n do 85         if (i<>j) then 86           if (x[i]<=x[j]) and (y[i]<=y[j]) then 87           begin 88             inc(len); 89             edge[len].point:=j+n; 90             inc(len); 91             add(j+n,i,1-edge[len-1].flow,0)  //添加原来没加的反向弧 92           end; 93  94     p[s]:=-1; 95     for i:=1 to n do   //下面很多处理的细节，不赘述，繁杂但不难想到 96     begin 97       if i=w then e:=0 else e:=1; 98       inc(len); 99       add(s,i+n,e,0);100       inc(len);101       add(i+n,s,1-e,0);102     end;103 //0 表示超级源点，s表示起点，t表示超级汇点104     t:=2*n+2;105     inc(len);106     add(0,s,1,0);107     inc(len);108     add(s,0,1,0);109     for i:=1 to n do   110     begin111       inc(len);112       add(i+n,i,pref[i],1);113       inc(len);114       add(i,i+n,1-pref[i],-1);115       if max=i then e:=0   116       else e:=1;117       inc(len);118       add(i,t,e,0);119       inc(len);120       add(t,i,1-e,0);121     end;122   end;123 124 function spfa:boolean;125   var f,r,x,y,i,j,head,tail:longint;126   begin127     fillchar(v,sizeof(v),false);128     for i:=0 to t do129       d[i]:=-mo;130     d[0]:=0;131     q[0]:=0;132     f:=0;133     r:=0;134     head:=1;135     tail:=1;136     while head<=tail do  //缩空间的写法，好久没这么写了137     begin138       x:=q[f];139       v[x]:=false;140       i:=p[x];141       while i<>-1 do142       begin143         y:=edge[i].point;144         if edge[i].flow>0 then145         begin146           if d[x]+edge[i].cost>d[y] then147           begin148             d[y]:=edge[i].cost+d[x];149             pre[y]:=x;150             cur[y]:=i;151             if not v[y] then152             begin153               v[y]:=true;154               r:=(r+1) mod mo;155               inc(tail);156               q[r]:=y;157             end;158           end;159         end;160         i:=edge[i].next;161       end;162       f:=(f+1) mod mo;163       inc(head);164     end;165     if d[t]=-mo then exit(false) else exit(true);166   end;167 168 function mincost:longint;  //最大费用最大流169   var i,j:longint;170   begin171     be:=d[max];172     mincost:=be;   //预处理出来的费用173     while spfa do174     begin175       mincost:=mincost+d[t];176       i:=t;177       while i<>0 do178       begin179         j:=cur[i];180         dec(edge[j].flow);181         inc(edge[j xor 1].flow);182         i:=pre[i];183       end;184     end;185   end;186 187 begin188   len:=-2;189   fillchar(p,sizeof(p),255);190   readln(n);191   for i:=1 to n do192     readln(x[i],y[i]);193   for i:=1 to n do194     for j:=1 to n do195       if (i<>j) then196         if (x[i]<=x[j]) and (y[i]<=y[j]) then197         begin198           len:=len+2;199           add(i,j,1,0);  //个人感觉这样建之后添加边更容易一点200           inc(rd[j]);201         end;202 203   s:=2*n+1;204   for i:=1 to n do205     if rd[i]=0 then206     begin207       len:=len+2;208       add(s,i,1,0);209       inc(rd[i]); 210     end;211 212   preflow;213   change;214   writeln(mincost);215 end.