CF 277E Binary Tree on Plane （拆點 + 費用流） （KM也可做），277ebinary
題目大意：
平面上有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
