Codeforces Round #170 (Div. 1) E. Binary Tree on Plane（最小费用流）

题目大意

给你平面上 n(2<=n<=400) 个点，要求用这些点组成一个二叉树(每个节点的儿子节点不超过两个)，定义每条边的权值为两个点之间的欧几里得距离。求一个权值和最小的二叉树，并输出这个权值

点 i 可以成为点 j 的的父亲的条件是：点 i 的 y 坐标比 j 的 y 坐标大！

如果不存在这样的二叉树，输出 -1

做法分析

转换成为最小费用流

1、把每个点 u 拆成两个点 u' 和 u''

2、增加源点 source 和汇点 sink

3、链接 source 和每个点 u'，即 <source, u'> 容量为 2，费用为 0

4、链接每个点 u'' 和 sink，即 <u'', sink> 容量为 1，费用为 0

5、对于每两个点 u 和 v，如果 u 的纵坐标大于 v 的纵坐标，建边 <u', v''> 容量为 1，费用为 u 和 v 的欧几里得距离

对建好的网络跑一遍最小费用最大流，如果流量 maxFlow!=n-1 那么无解，否则 minCost 就是一个最优解

参考代码

Binary Tree on Plane

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <queue>
  7 
  8 #define INT_INF 0x3fffffff
  9 #define N 900
 10 #define E 1000000
 11 
 12 using namespace std;
 13 
 14 struct Edge
 15 {
 16     int st, en, cap, flow, next;
 17     double cost;
 18     Edge() {}
 19     Edge(int a, int b, int c, double d, int e)
 20     {
 21         st=a, en=b, cap=c, cost=d, next=e, flow=0;
 22     }
 23 } edge[E];
 24 int head[N], tot, now[N], pre[N];
 25 int source, sink, FLOW, n;
 26 double dis[N];
 27 queue<int> q;
 28 bool vs[N];
 29 
 30 struct data
 31 {
 32     double x, y;
 33     bool operator <(const data &a) const
 34     {
 35         if(y==a.y) return x<a.x;
 36         else return y>a.y;
 37     }
 38 } vertex[N];
 39 
 40 void add_edge(int st,int en,int cap,double cost)
 41 {
 42     edge[tot]=Edge(st, en, cap, cost, head[st]);
 43     head[st]=tot++;
 44 
 45     edge[tot]=Edge(en, st, 0, -cost, head[en]);
 46     head[en]=tot++;
 47 }
 48 
 49 bool SPFA()
 50 {
 51     for(int i=source; i<=sink; i++)
 52         dis[i]=INT_INF, vs[i]=false, now[i]=-1;
 53 
 54     while(!q.empty()) q.pop();
 55     q.push(source), dis[source]=0, vs[source]=true;
 56     while(!q.empty())
 57     {
 58         int u=q.front();
 59         q.pop(), vs[u]=0;
 60         for(int i=head[u], v; i!=-1; i=edge[i].next)
 61             if(edge[i].cap-edge[i].flow>0 && dis[v=edge[i].en]>dis[u]+edge[i].cost)
 62             {
 63                 dis[v]=dis[u]+edge[i].cost, now[v]=i;
 64                 if(!vs[v]) vs[v]=1, q.push(v);
 65             }
 66     }
 67     if(dis[sink]!=INT_INF) return true;
 68     else return false;
 69 }
 70 
 71 double MCMF()
 72 {
 73     double cost=0;
 74     FLOW=0;
 75     while(SPFA())
 76     {
 77         int flow=INT_INF;
 78         for(int u=sink; u!=source; u=edge[now[u]].st)
 79             if(flow>edge[now[u]].cap-edge[now[u]].flow)
 80                 flow=edge[now[u]].cap-edge[now[u]].flow;
 81         for(int u=sink; u!=source; u=edge[now[u]].st)
 82         {
 83             edge[now[u]].flow+=flow;
 84             edge[now[u]^1].flow-=flow;
 85         }
 86         cost+=flow*dis[sink];
 87         FLOW+=flow;
 88     }
 89     return cost;
 90 }
 91 
 92 double cal_dis(int a, int b)
 93 {
 94     return sqrt((vertex[a].x-vertex[b].x)*(vertex[a].x-vertex[b].x)+(vertex[a].y-vertex[b].y)*(vertex[a].y-vertex[b].y));
 95 }
 96 
 97 void build(int n)
 98 {
 99     tot=0, source=0, sink=n+n+1;
100     for(int i=source; i<=sink; i++) head[i]=-1;
101     for(int i=1; i<=n; i++) add_edge(source, i, 2, 0), add_edge(i+n, sink, 1, 0);
102     for(int i=1; i<=n; i++)
103         for(int j=i+1; j<=n; j++)
104         {
105             if(vertex[i].y==vertex[j].y) continue;
106             add_edge(i, j+n, 1, cal_dis(i, j));
107         }
108 }
109 
110 int main()
111 {
112     scanf("%d", &n);
113     for(int i=1; i<=n; i++) scanf("%lf%lf", &vertex[i].x, &vertex[i].y);
114     sort(vertex+1, vertex+n+1);
115 
116     build(n);
117     double ans=MCMF();
118 
119     if(FLOW!=n-1) printf("-1\n");
120     else printf("%lf\n",ans);
121     return 0;
122 }

AC通道

Codeforces Round #170 (Div. 1) E. Binary Tree on Plane