一开始我觉得这不是一个弱弱的费用流吗？
每个豆豆拆点，入点出点随便连连
由于肯定是DAG图，边权为正的最大费用肯定能增广出来
于是我们只要跑总流量为2的最大费用最大流不就行了吗
但是
这样会TLE，因为会出现稠密图，spfa跑稠密图太慢
既然这样，能不能换一个找增广路的方法呢？
最大路径更快的方法就是DAG图的拓扑排序+dp
但好像无法处理反向弧导致带来的环啊
那既然这样，反正总流量很小，
我们可以用DAG解决最大路径特有的dp找第一条增广路（因为这时候是肯定的DAG），跑出一个较大费用
然后再用spfa增广呢？这样就大大减小了时间复杂度
这就是AC方法
注意这道题空间卡的较紧，能开integer不要开longint
实现起来要小心
const mo=;
type node=record
next:longint;
point,flow,cost:integer;
end; var edge:array[..] of node;
v:array[..] of boolean;
d,rd,pre,pref:array[..] of integer;
q:array[..] of integer;
p,x,y,cur:array[..] of longint;
len:longint;
max,s,t,i,j,n,m,be:integer; procedure add(x,y,f,c:integer);
begin
edge[len].point:=y;
edge[len].flow:=f;
edge[len].cost:=c;
edge[len].next:=p[x];
p[x]:=len;
end; procedure preflow;
var x,y,f,r,i,j:longint;
begin
r:=;
f:=;
q[]:=s;
while f<=r do //拓扑排序
begin
x:=q[f];
i:=p[x];
while i<>- do
begin
y:=edge[i].point;
dec(rd[y]);
if (rd[y]=) then
begin
inc(r);
q[r]:=y;
end;
i:=edge[i].next;
end;
inc(f);
end;
fillchar(d,sizeof(d),);
d[s]:=;
for j:= to r do //DAG图根据拓扑的顺序dp解决最大路径
begin
x:=q[j];
i:=p[x];
while i<>- do
begin
y:=edge[i].point;
if d[y]<d[x]+ then
begin
d[y]:=d[x]+;
pre[y]:=x;
cur[y]:=i;
if d[y]>d[max] then max:=y;
end;
i:=edge[i].next;
end;
end;
end; procedure change; //建立预处理后的网络继续增广
var i,j,e,w:longint;
begin
for i:= to n do
pref[i]:=;
i:=max;
while i<>s do //相当于找到第一条增广路然后弄一弄反向弧什么的
begin
pref[i]:=;
j:=cur[i];
dec(edge[j].flow);
if pre[i]=s then w:=i;
i:=pre[i];
end;
len:=-;
for i:= to n do
for j:= to n do
if (i<>j) then
if (x[i]<=x[j]) and (y[i]<=y[j]) then
begin
inc(len);
edge[len].point:=j+n;
inc(len);
add(j+n,i,-edge[len-].flow,) //添加原来没加的反向弧
end; p[s]:=-;
for i:= to n do //下面很多处理的细节，不赘述，繁杂但不难想到
begin
if i=w then e:= else e:=;
inc(len);
add(s,i+n,e,);
inc(len);
add(i+n,s,-e,);
end;
// 表示超级源点，s表示起点，t表示超级汇点
t:=*n+;
inc(len);
add(,s,,);
inc(len);
add(s,,,);
for i:= to n do
begin
inc(len);
add(i+n,i,pref[i],);
inc(len);
add(i,i+n,-pref[i],-);
if max=i then e:=
else e:=;
inc(len);
add(i,t,e,);
inc(len);
add(t,i,-e,);
end;
end; function spfa:boolean;
var f,r,x,y,i,j,head,tail:longint;
begin
fillchar(v,sizeof(v),false);
for i:= to t do
d[i]:=-mo;
d[]:=;
q[]:=;
f:=;
r:=;
head:=;
tail:=;
while head<=tail do //缩空间的写法，好久没这么写了
begin
x:=q[f];
v[x]:=false;
i:=p[x];
while i<>- do
begin
y:=edge[i].point;
if edge[i].flow> then
begin
if d[x]+edge[i].cost>d[y] then
begin
d[y]:=edge[i].cost+d[x];
pre[y]:=x;
cur[y]:=i;
if not v[y] then
begin
v[y]:=true;
r:=(r+) mod mo;
inc(tail);
q[r]:=y;
end;
end;
end;
i:=edge[i].next;
end;
f:=(f+) mod mo;
inc(head);
end;
if d[t]=-mo then exit(false) else exit(true);
end; function mincost:longint; //最大费用最大流
var i,j:longint;
begin
be:=d[max];
mincost:=be; //预处理出来的费用
while spfa do
begin
mincost:=mincost+d[t];
i:=t;
while i<> do
begin
j:=cur[i];
dec(edge[j].flow);
inc(edge[j xor ].flow);
i:=pre[i];
end;
end;
end; begin
len:=-;
fillchar(p,sizeof(p),);
readln(n);
for i:= to n do
readln(x[i],y[i]);
for i:= to n do
for j:= to n do
if (i<>j) then
if (x[i]<=x[j]) and (y[i]<=y[j]) then
begin
len:=len+;
add(i,j,,); //个人感觉这样建之后添加边更容易一点
inc(rd[j]);
end; s:=*n+;
for i:= to n do
if rd[i]= then
begin
len:=len+;
add(s,i,,);
inc(rd[i]);
end; preflow;
change;
writeln(mincost);
end.