題目大意：平面上有n個點，兩兩不同。現在給出二叉樹的定義，要求樹邊一定是從上指向下，即從y坐標大的點指向小的點，並且每個結點至多有兩個兒子。現在讓你求給出的這些點是否能構成一棵二叉樹，如果能，使二叉樹的樹邊長度（歐幾里德長度）總和最小，輸出這個總和。如果不能，輸出-1.答案與標準答案相差1e-6內都...
題目大意：
平面上有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\n", 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\n", 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\n", ans); 127 else puts("-1"); 128 129 return 0; 130 }Accepted
噁心的提交：自己真的很渣QAQ
