Codefoces 277 E. Binary Tree on Plane

题目链接：http://codeforces.com/problemset/problem/277/E
参考了这篇题解：http://blog.csdn.net/Sakai_Masato/article/details/50775315
没看出来是费用流啊...我好菜啊。
我写得有一点和上面这篇题解不同：在判断是否无解时我直接记录最大流，判断最大流是否等于$n-1$(似乎是等价的...)
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<vector>
  5 #include<cstdlib>
  6 #include<cmath>
  7 #include<cstring>
  8 using namespace std;
  9 #define maxn 1010
 10 #define inf 0x7fffffff
 11 #define llg int
 12 #define sqr(_) ((_)*(_))
 13 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
 14 llg n,m;
 15 
 16 struct node 
 17 {
 18     llg u,v,c,next;
 19     double w;
 20 };
 21 
 22 struct FLOW
 23 {
 24     llg cnt,maxflow,S,T,pre[maxn],N;
 25     llg head[maxn],dl[maxn*maxn];
 26     bool bj[maxn];
 27     double mincost,dis[maxn];
 28     node e[maxn*maxn];
 29 
 30 
 31     void init()
 32     {
 33         memset(head,-1,sizeof(head));
 34         mincost=cnt=maxflow=0;
 35         maxflow=0; mincost=0;
 36     }
 37 
 38     void link(llg u,llg v,double w,llg c)
 39     {
 40         e[cnt].u=u,e[cnt].v=v,e[cnt].w=w,e[cnt].c=c;
 41         e[cnt].next=head[u],head[u]=cnt++;
 42         
 43         e[cnt].u=v,e[cnt].v=u,e[cnt].w=-w,e[cnt].c=0;
 44         e[cnt].next=head[v],head[v]=cnt++;
 45     }
 46 
 47     void updata()
 48     {
 49         llg f=inf;
 50         for (llg i=T;i!=S;i=e[pre[i]].u) f=min(f,e[pre[i]].c);
 51         maxflow+=f;
 52         for (llg i=T;i!=S;i=e[pre[i]].u)
 53         {
 54             e[pre[i]].c-=f;
 55             e[pre[i]^1].c+=f;
 56             mincost+=(double)f*e[pre[i]].w;
 57         }
 58     }
 59 
 60     bool spfa()
 61     {
 62         llg u,v;
 63         double w;
 64         memset(pre,-1,sizeof(pre));
 65         memset(bj,0,sizeof(bj));
 66         for (llg i=0;i<=N;i++) dis[i]=inf;
 67         llg l=0,r=1;
 68         dl[r]=S; bj[S]=1; dis[S]=0;
 69         do
 70         {
 71             bj[u=dl[++l]]=0;
 72             for (llg i=head[u];i!=-1;i=e[i].next)
 73             {
 74                 v=e[i].v,w=e[i].w;
 75                 if (e[i].c && dis[v]>dis[u]+w)
 76                 {
 77                     dis[v]=dis[u]+w;
 78                     pre[v]=i;
 79                     if (!bj[v]) bj[v]=1,dl[++r]=v;
 80                 }
 81             }
 82         }while (l<r);
 83     
 84         if (pre[T]==-1) return 0;
 85         return 1;
 86     }
 87     
 88     void work()
 89     {
 90         while (spfa()) 
 91             updata();
 92     }
 93 
 94 }G;
 95 
 96 inline int getint()
 97 {
 98     int w=0,q=0; char c=getchar();
 99     while((c<'0' || c>'9') && c!='-') c=getchar(); if(c=='-') q=1,c=getchar(); 
100     while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); return q ? -w : w;
101 }
102 
103 struct POINT{double x,y;}po[maxn];
104 
105 bool cmp(const POINT&x,const POINT&y) {return x.y==y.y?x.x<y.x:x.y<y.y;}
106 
107 double dis(const POINT&x,const POINT&y) {return sqrt(sqr(x.x-y.x)+sqr(x.y-y.y));}
108 
109 int main()
110 {
111     yyj("flow");
112     cin>>n;
113     G.init();
114     G.N=n*2+10;
115     for (llg i=1;i<=n;i++) scanf("%lf%lf",&po[i].x,&po[i].y);
116     sort(po+1,po+n+1,cmp);
117     reverse(po+1,po+1+n);
118     for (llg i=1;i<=n;i++)
119         for (llg j=i+1;j<=n;j++)
120             if (po[i].y>po[j].y)
121                 G.link(i,j+n,dis(po[i],po[j]),(llg)1);
122     G.S=2*n+1,G.T=2*n+2;
123     for (llg i=1;i<=n;i++)
124     {
125         G.link(G.S,i,0,(llg)2);
126         G.link(i+n,G.T,0,(llg)1);
127     }
128     G.work();
129     if (G.maxflow!=n-1) {cout<<-1;} else printf("%.9lf",G.mincost);
130     return 0;
131 }