CF 277E Binary Tree on Plane （拆点 + 费用流）（KM也可做）

题目大意：

平面上有n个点，两两不同。现在给出二叉树的定义，要求树边一定是从上指向下，即从y坐标大的点指向小的点，并且每个结点至多有两个儿子。现在让你求给出的这些点是否能构成一棵二叉树，如果能，使二叉树的树边长度（欧几里德长度）总和最小，输出这个总和。如果不能，输出-1.答案与标准答案相差1e-6内都认为是正确的。

算法讨论：

起初是这样想的，肯定是MCMF，费用是距离，然后流量一开始我是这样搞的：从父亲向儿子连流量为2的边。但是你会发现这样有一个问题，就是如果某个结点如果真的有两个儿子的话，那么这个父亲与他的父亲之间的边的距离就会被加进去两次。表示不会解决这个问题，各种头痛。最后只得参见题解，是把一个点拆成两个点A[i] 和 B[i]， S(超级源点)连向 A[i]，流量为1，花费为0，B[i]全部连向T(超级汇点)，流量为2，花费为0，然后扫描下，如果j满足成为i儿子的条件时，就把A[j]连向B[i]，流量为1，花费为距离。注意精度问题。

至于判断是否可以是棵二叉树，我们在流完之后判断一下流量是否等于n-1就可以了。自己原来还傻子一样的去判断。

注意：

这个题如果用spfa的费用流的话，很容易写T,推荐用ZKW费用流（跑起来如飞一样，因为跑二分图特别快），但是网上的模板太不可信，找了5个，错了4个。所以自己精心翻译了一个模板。求不喷。

好像说把B[I]再次拆点，用KM就可以做了。表示自己不会KM。。学下吧。

Codes:

SPFA费用流（邻接表STL版）（TLE ON TEST 23）

  1 #include <queue>
  2 #include <cmath>
  3 #include <vector>
  4 #include <cstdio>
  5 #include <cstring>
  6 #include <cstdlib>
  7 #include <iostream>
  8 #include <algorithm>
  9 using namespace std;
 10 
 11 int n;
 12 bool flag = false;
 13 
 14 struct Edge{
 15     int from, to, cap, flow;
 16     double cost;
 17     Edge(int _from=0, int _to=0, int _cap=0, int _flow=0, double _cost=0):
 18         from(_from), to(_to), cap(_cap), flow(_flow), cost(_cost) {}
 19 };
 20 
 21 struct Point{
 22     int x, y;
 23     Point(int _x = 0, int _y = 0): x(_x), y(_y) {}
 24     bool operator < (const Point &a) const {
 25         if(y == a.y) return x < a.x;
 26         return y > a.y;
 27     }
 28 }p[405];
 29 
 30 struct MCMF{
 31     static const int N = 800 + 5;
 32     static const int M = 40000 + 5;
 33     static const int oo = 0x3f3f3f3f;
 34     
 35     int n, m, s, t;
 36     vector <Edge> edges;
 37     vector <int> G[N];
 38     int inque[N], pre[N], a[N];
 39     double dis[N];
 40     
 41     void Clear(){
 42         for(int i = 0; i <= n + 1; ++ i) G[i].clear();
 43         edges.clear();
 44     }
 45     void Add(int from, int to, int cp, int flw, double ct){
 46         edges.push_back((Edge){from, to, cp, 0, ct});
 47         edges.push_back((Edge){to, from, 0, 0, -ct});
 48         int m = edges.size();
 49         G[from].push_back(m - 2);
 50         G[to].push_back(m - 1);
 51     }
 52     bool bfs(int &flw, double &ct){
 53         for(int i = 0; i <= n + 1; ++ i) dis[i] = oo;
 54         memset(inque, 0, sizeof inque);
 55         dis[s] = 0; a[s] = oo; inque[s] = 1; pre[s] = 0;
 56         
 57         queue <int> q;
 58         q.push(s);
 59         while(!q.empty()){
 60             int x = q.front(); q.pop();
 61             inque[x] = 0;
 62             for(int i = 0; i < G[x].size(); ++ i){
 63                 Edge &e = edges[G[x][i]]; 
 64                 if(e.cap > e.flow && dis[e.to] > dis[x] + e.cost){
 65                     dis[e.to] = dis[x] + e.cost;
 66                     pre[e.to] = G[x][i];
 67                     a[e.to] = min(a[x], e.cap - e.flow);
 68                     if(!inque[e.to]){
 69                         q.push(e.to);inque[e.to] = 1;
 70                     }
 71                 }
 72             }
 73         }
 74         if(dis[t] == (double)oo) return false;
 75         flw += a[t];
 76         ct += (double) dis[t] * a[t];
 77         
 78         int now = t;
 79         while(now != s){
 80             edges[pre[now]].flow += a[t];
 81             edges[pre[now]^1].flow -= a[t];
 82             now = edges[pre[now]].from;
 83         }
 84         return true;
 85     }
 86     double MinCostMaxFlow(int s, int t){
 87         this->s = s;this->t = t;
 88         int flw = 0;
 89         double ct = 0;
 90         while(bfs(flw, ct));
 91         if(flw == (n / 2 - 1)) flag = true;
 92         return ct;
 93     }
 94 }Net;
 95 
 96 double dist(int i, int j){
 97     return sqrt(pow(p[i].x - p[j].x, 2) + pow(p[i].y - p[j].y, 2));
 98 }
 99 
100 int main(){
101     scanf("%d", &n);
102     Net.n = n * 2;
103     for(int i = 1; i <= n; ++ i)
104         scanf("%d%d", &p[i].x, &p[i].y);
105     
106     sort(p + 1, p + n + 1);
107     for(int i = 1; i <= n; ++ i)
108         Net.Add(0, i, 1, 0, 0);
109     for(int i = n + 1; i <= n + n; ++ i)
110         Net.Add(i, n + n + 1, 2, 0, 0);
111     for(int i = 1; i <= n; ++ i){
112         for(int j = i + 1; j <= n; ++ j){
113             if(p[i].y > p[j].y)
114                 Net.Add(j, i + n, 1, 0, dist(i, j));
115         }
116     }
117     
118     double ans = Net.MinCostMaxFlow(0, Net.n + 1);
119     if(flag) printf("%.15lf
", ans);
120     else puts("-1");
121     
122     return 0;
123 }

ＳＴＬ

SPFA费用流（邻接表数组版）（TLE ON TEST 23）

  1 #include <deque>
  2 #include <cmath>
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <cstdlib>
  6 #include <iostream>
  7 #include <algorithm>
  8 using namespace std;
  9 
 10 int n;
 11 bool flag = false;
 12 
 13 struct Edge{
 14     int from, to, cap, flow;
 15     double cost;
 16     Edge(int _from=0, int _to=0, int _cap=0, int _flow=0, double _cost=0):
 17         from(_from), to(_to), cap(_cap), flow(_flow), cost(_cost) {}
 18 };
 19 
 20 struct Point{
 21     int x, y;
 22     Point(int _x = 0, int _y = 0): x(_x), y(_y) {}
 23     bool operator < (const Point &a) const {
 24         if(y == a.y) return x < a.x;
 25         return y > a.y;
 26     }
 27 }p[405];
 28 
 29 struct MCMF{
 30     static const int N = 800 + 5;
 31     static const int M = 320000 + 5;
 32     static const int oo = 0x3f3f3f3f;
 33     
 34     int n, m, s, t, tim, tot;
 35     int first[N], next[M];
 36     int u[M], v[M], cap[M], flow[M];
 37     double cost[M];
 38     int inque[N], pre[N], a[N];
 39     double dis[N];
 40     
 41     void Clear(){
 42         tot = 0;
 43         for(int i = 0; i <= n; ++ i) first[i] = -1;
 44     }
 45     void Add(int from, int to, int cp, int flw, double ct){
 46         u[tot] = from; v[tot] = to; cap[tot] = cp; flow[tot] = 0; cost[tot] = ct;
 47         next[tot] = first[u[tot]]; first[u[tot]] = tot; tot ++;
 48         u[tot] = to; v[tot] = from; cap[tot] = 0; flow[tot] = 0; cost[tot] = -ct;
 49         next[tot] = first[u[tot]]; first[u[tot]] = tot; tot ++;
 50     }
 51     bool bfs(int &flw, double &ct){
 52         for(int i = 0; i <= n + 1; ++ i) dis[i] = oo;
 53         
 54         ++ tim;
 55         dis[s] = 0; a[s] = oo; inque[s] = tim; pre[s] = 0;
 56         deque <int> q;
 57         q.push_back(s);
 58         
 59         while(!q.empty()){
 60             int x = q.front(); q.pop_front();
 61             inque[x] = 0;
 62             for(int i = first[x]; i != -1; i = next[i]){
 63                 if(cap[i] > flow[i] && dis[v[i]] > dis[x] + cost[i]){
 64                     dis[v[i]] = dis[x] + cost[i];
 65                     pre[v[i]] = i;
 66                     a[v[i]] = min(a[x], cap[i] - flow[i]);
 67                     
 68                     if(inque[v[i]] != tim){
 69                         inque[v[i]] = tim;
 70                         if(!q.empty() && dis[v[i]] < dis[q.front()]) 
 71                             q.push_front(v[i]);
 72                         else    q.push_back(v[i]);
 73                     }
 74                 }
 75             }
 76         }
 77         if(dis[t] == oo) return false;
 78         flw += a[t];
 79         ct += (double) dis[t] * a[t];
 80         
 81         int now = t;
 82         while(now != s){
 83             flow[pre[now]] += a[t];
 84             flow[pre[now]^1] -= a[t];
 85             now = u[pre[now]];
 86         }
 87         return true;
 88     }
 89     double MinCostMaxFlow(int s, int t){
 90         this->s = s;this->t = t;
 91         int flw = 0;
 92         double ct = 0;
 93         while(bfs(flw, ct));
 94         if(flw == (n / 2 - 1)) flag = true;
 95         return ct;
 96     }
 97 }Net;
 98 
 99 double dist(int i, int j){
100     return sqrt(pow(p[i].x - p[j].x, 2) + pow(p[i].y - p[j].y, 2));
101 }
102 
103 int main(){
104     scanf("%d", &n);
105     Net.n = n * 2;
106     Net.Clear();
107     for(int i = 1; i <= n; ++ i)
108         scanf("%d%d", &p[i].x, &p[i].y);
109     
110     sort(p + 1, p + n + 1);
111     for(int i = 1; i <= n; ++ i)
112         Net.Add(0, i, 1, 0, 0);
113     for(int i = n + 1; i <= n + n; ++ i)
114         Net.Add(i, n + n + 1, 2, 0, 0);
115     for(int i = 1; i <= n; ++ i){
116         for(int j = i + 1; j <= n; ++ j){
117             if(p[i].y > p[j].y)
118                 Net.Add(j, i + n, 1, 0, dist(i, j));
119         }
120     }
121     
122     double ans = Net.MinCostMaxFlow(0, Net.n + 1);
123     if(flag) printf("%.15lf
", ans);
124     else puts("-1");
125     
126     return 0;
127 }

数组版

ZKW费用流（邻接表数组版）（Accepted）

  1 #include <deque>
  2 #include <cmath>
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <cstdlib>
  6 #include <iostream>
  7 #include <algorithm>
  8 using namespace std;
  9 
 10 int n;
 11 double ans = 0, cst = 0;
 12 bool flag = false;
 13 
 14 struct Edge{
 15     int from, to, cap, flow;
 16     double cost;
 17     Edge(int _from=0, int _to=0, int _cap=0, int _flow=0, double _cost=0):
 18         from(_from), to(_to), cap(_cap), flow(_flow), cost(_cost) {}
 19 };
 20 
 21 struct Point{
 22     int x, y;
 23     Point(int _x = 0, int _y = 0): x(_x), y(_y) {}
 24     bool operator < (const Point &a) const {
 25         if(y == a.y) return x < a.x;
 26         return y > a.y;
 27     }
 28 }p[405];
 29 
 30 struct MCMF{
 31     static const int N = 800 + 5;
 32     static const int M = 320000 + 5;
 33     static const int oo = 0x3f3f3f3f;
 34     
 35     int n, m, s, t, tim, tot;
 36     int first[N], next[M];
 37     int u[M], v[M], cap[M];
 38     double cost[M], dis[N];
 39     bool vi[N];int cur[N];
 40     
 41     void Clear(){
 42         tot = 0;
 43         for(int i = 0; i <= n; ++ i) first[i] = -1;
 44     }
 45     void Add(int from, int to, int cp, int flw, double ct){
 46         u[tot] = from; v[tot] = to; cap[tot] = cp; cost[tot] = ct;
 47         next[tot] = first[u[tot]]; first[u[tot]] = tot; tot ++;
 48         u[tot] = to; v[tot] = from; cap[tot] = 0; cost[tot] = -ct;
 49         next[tot] = first[u[tot]]; first[u[tot]] = tot; tot ++;
 50     }
 51     int aug(int x, int f){
 52         if(x == t){
 53             ans += (double)cst * f;
 54             return f;
 55         }
 56          
 57         vi[x] = true;
 58         int tmp = f;
 59         for(int i = first[x]; i != -1; i = next[i])
 60             if(cap[i] && !vi[v[i]] && !cost[i]){
 61                 int delta = aug(v[i], tmp < cap[i] ? tmp : cap[i]);
 62                 cap[i] -= delta;
 63                 cap[i^1] += delta;
 64                 tmp -= delta;
 65                 if(tmp == 0) return f;
 66             }
 67         return f - tmp;
 68     }
 69     bool modlabel(){
 70         double tmp = (double) oo;
 71         for(int i = 0; i <= n; ++ i){
 72             if(vi[i])
 73                 for(int j = first[i]; j != -1; j = next[j])
 74                     if(cap[j] && !vi[v[j]] && cost[j] < tmp)
 75                         tmp = cost[j];
 76         }
 77         
 78         if(tmp == (double)oo) return false;
 79         for(int i = 0; i <= n; ++ i)
 80             if(vi[i])
 81                 for(int j = first[i]; j != -1; j = next[j])
 82                     cost[j] -= tmp, cost[j^1] += tmp;
 83         cst += tmp;
 84         return true;
 85     }
 86     void MinCostMaxFlow(int s, int t){
 87         this->s = s; this->t = t;
 88         int flw, tot=0;
 89         for(;;){
 90             memset(vi, false, sizeof vi);
 91             while(flw = aug(s, oo)){
 92                 tot += flw;
 93                 memset(vi, false, sizeof vi);
 94             }
 95             
 96             if(!modlabel()) break;
 97         }
 98         if(tot == (n / 2 - 1)) flag = true;
 99     }
100 }Net;
101 
102 double dist(int i, int j){
103     return sqrt(pow(p[i].x - p[j].x, 2) + pow(p[i].y - p[j].y, 2));
104 }
105 
106 int main(){
107 
108     scanf("%d", &n);
109     Net.n = n * 2;
110     Net.Clear();
111     for(int i = 1; i <= n; ++ i)
112         scanf("%d%d", &p[i].x, &p[i].y);
113         
114     sort(p + 1, p + n + 1);
115     for(int i = 1; i <= n; ++ i)
116         Net.Add(0, i, 1, 0, 0);
117     for(int i = n + 1; i <= n + n; ++ i)
118         Net.Add(i, n + n + 1, 2, 0, 0);
119     for(int i = 1; i <= n; ++ i){
120         for(int j = i + 1; j <= n; ++ j){
121             if(p[i].y > p[j].y)
122                 Net.Add(j, i + n, 1, 0, dist(i, j));
123         }
124     }
125     Net.MinCostMaxFlow(0, Net.n + 1);
126     if(flag) printf("%.15lf
", ans);
127     else puts("-1");
128     
129     return 0;
130 }

Accepted

恶心的提交：自己真的很渣QAQ

CF 277E Binary Tree on Plane （拆点 + 费用流） （KM也可做）

CF 277E Binary Tree on Plane （拆点 + 费用流）（KM也可做）