#include #include #include #include #include #include using namespace std; struct point{ int x; int y; }; struct memo_pair{ double val; int iter; }; int cur_iter = 0; memo_pair Memo[66000][20]; bool seen[66000]; int sets[66000]; double dist(point p, point q){ return sqrt(pow(p.x-q.x,2) + pow(p.y-q.y,2)); } void Print_Vector(const vector& v){ for(int i = 0; i < v.size(); i++) cout << v[i] << " "; cout << endl; } void Print_2D_Vector(const vector >& v){ for(int i = 0; i < v.size(); i++){ for(int j = 0; j < v[i].size(); j++) cout << v[i][j] << " "; cout << endl; } } void Print_2D_Vector(const vector >& v){ for(int i = 0; i < v.size(); i++){ for(int j = 0; j < v[i].size(); j++) cout << v[i][j] << " "; cout << endl; } } void Build_Distances(const vector& v, vector >& distances){ distances.resize(v.size()); for(int i = 0; i < v.size(); i++){ distances[i].resize(v.size()); for(int j = 0; j < v.size(); j++) distances[i][j] = dist(v[i], v[j]); } } double TSP(const vector >& G){ cur_iter++; fill(seen, seen+66000, false); vector powers_of_2(G.size()); for(int i = 0; i < G.size(); i++) powers_of_2[i] = pow(2, i); int set_write_pos = 0; for(int i = 1; i < G.size(); i++){ int cur = powers_of_2[i]; Memo[cur][i].val = G[0][i]; Memo[cur][i].iter = cur_iter; for(int j = i; j < G.size(); j++){ if(i != j){ double new_set = cur + powers_of_2[j]; sets[set_write_pos] = new_set; set_write_pos++; } } } int set_read_pos = 0; while(set_read_pos < set_write_pos){ int S = sets[set_read_pos]; set_read_pos++; for(int i = 1; i < G.size(); i++){ int i_mask = powers_of_2[i]; if(Memo[S][i].iter != cur_iter){ if((S&i_mask) != 0){ // i is in S double min = 500000; for(int j = 1; j < G.size(); j++){ int j_mask = powers_of_2[j]; if(i != j && (S&j_mask) != 0){ // j is also in S int without_i = S-i_mask; double cur_val = Memo[without_i][j].val + G[i][j]; if(cur_val < min) min = cur_val; } } if(min < 0) cout <<"uh-oh" << endl; Memo[S][i].val = min; Memo[S][i].iter = cur_iter; } else{ // i is not in S, so add it to S for the next largest set of S's int new_set = S+i_mask; if(!seen[new_set]){ sets[set_write_pos] = new_set; set_write_pos++; seen[new_set] = true; } } } } } double min = 500000; int S = pow(2, G.size())-2; for(int i = 1; i < G.size(); i++){ double cur = Memo[S][i].val + G[i][0]; if(cur < min) min = cur; } return min; } bool Find_Path(const vector >& g, const vector >& f, vector& path){ //Print_2D_Vector(g); vector seen(g.size()); vector parent(g.size(), -1); parent[0] = -1; seen[0] = true; deque frontier; frontier.push_back(0); bool found = false; while(!found && !frontier.empty()){ int cur = frontier.front(); frontier.pop_front(); if(cur == g.size()-1) found = true; else{ for(int i = 0; i < g.size(); i++){ if(g[cur][i] && !seen[i] && (( cur < i && f[cur][i] == 0) || cur > i && f[i][cur] == 1)){ seen[i] = true; parent[i] = cur; frontier.push_back(i); } } } } if(found){ path.resize(0); int cur = g.size()-1; path.push_back(cur); while(cur != 0){ path.push_back(parent[cur]); cur = parent[cur]; } reverse(path.begin(), path.end()); } return found; } void Create_Zero_Matching(const vector >& g, vector& matching){ vector > bipartite(2*g.size()+2); for(int i = 0; i < bipartite.size(); i++) bipartite[i].resize(2*g.size()+2, false); for(int i = 1; i <= g.size(); i++){ bipartite[0][i] = true; } for(int i = g.size()+1; i < bipartite.size()-1; i++) bipartite[i][bipartite.size()-1] = true; for(int i = 0; i < g.size(); i++) for(int j = 0; j < g.size(); j++){ if(g[i][j] == 0){ bipartite[i+1][j+g.size()+1] = true; bipartite[j+g.size()+1][i+1] = true; } } vector > f(bipartite.size()); for(int i = 0; i < f.size(); i++) f[i].resize(bipartite.size(), 0); vector path; while(Find_Path(bipartite,f, path)){ for(int i = 0; i < path.size()-1; i++){ if(path[i] < path[i+1]) f[path[i]][path[i+1]]++; else f[path[i+1]][path[i]]--; } } matching.resize(0); for(int i = 1; i < f.size(); i++){ for(int j = 0; j < f.size()-1; j++){ if(f[i][j] != 0){ point p; p.x = i; p.y = j; matching.push_back(p); } } } } bool Find(const vector& v, const point& key){ for(int i = 0; i < v.size(); i++) if(v[i].x == key.x && v[i].y == key.y) return true; return false; } void Vertex_Cover(const vector >& grid, const vector& matches, vector& r_in_cover, vector& c_in_cover){ r_in_cover.resize(grid.size(), false); c_in_cover.resize(grid.size(), false); for(int i = 0; i < matches.size(); i++){ r_in_cover[matches[i].x-1] = true; } vector r_seen (grid.size(), false); vector c_seen (grid.size(), false); for(int i = 0; i < r_in_cover.size(); i++){ if(!r_seen[i] && !r_in_cover[i]){ deque frontier; frontier.push_back(i); r_seen[i] = true; while(!frontier.empty()){ int cur = frontier.front(); frontier.pop_front(); for(int j = 0; j < grid.size(); j++){ point p; p.x = i+1; p.y = j+grid.size()+1; if(!c_seen[j] && grid[cur][j] == 0 && !Find(matches, p)){ c_seen[j] = true; c_in_cover[j] = true; for(int k = 0; k < matches.size(); k++){ if(!r_seen[matches[k].x-1] && matches[k].y - grid.size()-1 == j){ frontier.push_back(matches[k].x-1); r_seen[matches[k].x-1] = true; r_in_cover[matches[k].x-1] = false; } } } } } } } } void Create_Matching(const vector >& costs, vector& matching){ matching.resize(costs.size()/2); vector > grid(costs.size()/2); for(int i = 0; i < grid.size(); i++){ grid[i].resize(costs.size()/2); for(int j = 0; j < grid[i].size(); j++){ grid[i][j] = costs[i][j+costs.size()/2]; } } // subtract row minima for(int i = 0; i < grid.size(); i++){ double min_val = 500000; for(int j = 0; j < grid.size(); j++){ double cur = grid[i][j]; if(cur < min_val){ min_val = cur; } } for(int j = 0; j < grid.size(); j++) grid[i][j] = grid[i][j] - min_val; } // subtract col minima for(int j = 0; j < grid.size(); j++){ double min_val = 500000; for(int i = 0; i < grid.size(); i++){ double cur = grid[i][j]; if(cur < min_val){ min_val = cur; } } for(int i = 0; i < grid.size(); i++){ grid[i][j] = grid[i][j] - min_val; } } vector zero_matching; Create_Zero_Matching(grid, zero_matching); while(zero_matching.size() != grid.size()){ double min = 500000; vector r_in_matching; vector c_in_matching; Vertex_Cover(grid, zero_matching, r_in_matching, c_in_matching); // Print_Vector(r_in_matching); //Print_Vector(c_in_matching); for(int i = 0; i < grid.size(); i++) for(int j = 0; j < grid.size(); j++){ if(!r_in_matching[i] && !c_in_matching[j]){ if(grid[i][j] < min) min = grid[i][j]; } } for(int i = 0; i < grid.size(); i++) for(int j = 0; j < grid.size(); j++){ if(!r_in_matching[i] && !c_in_matching[j]){ grid[i][j] = grid[i][j] - min; } if(r_in_matching[i] && c_in_matching[j]){ grid[i][j] = grid[i][j] + min; } } Create_Zero_Matching(grid, zero_matching); } matching.resize(grid.size()); for(int i = 0; i < zero_matching.size(); i++){ matching[zero_matching[i].x-1] = zero_matching[i].y-1; } } int main(){ int d; cin >> d; vector > tours(d); for(int i = 0; i < d; i++){ int n; cin >> n; tours[i].resize(n); for(int j = 0; j < n; j++){ cin >> tours[i][j].x; cin >> tours[i][j].y; } } double before_cost = 0; for(int i = 0; i < tours.size(); i++){ vector >distances; Build_Distances(tours[i], distances); before_cost = before_cost + TSP(distances); } // cout << "before = " << before_cost << endl; vector > bipartite_costs(d); bipartite_costs.resize(d); for(int i = 0; i < d; i++){ bipartite_costs[i].resize(d,0); } for(int i = 0; i < d/2; i++){ for(int j = d/2; j combined = tours[i]; combined.insert(combined.end(), tours[j].begin(), tours[j].end()); vector >distances; Build_Distances(combined, distances); double cur = TSP(distances); //cout << "i: " << i << "j: " << j << endl; bipartite_costs[i][j] = cur; bipartite_costs[j][i] = cur; } } //Print_2D_Vector(bipartite_costs); vector bipartite_matching(d); Create_Matching(bipartite_costs, bipartite_matching); double after_cost = 0; for(int i = 0; i < d/2; i++){ after_cost = after_cost + bipartite_costs[i][bipartite_matching[i]]; } //cout << "after: " << after_cost << endl; cout << fixed << setprecision(6) << before_cost << " " << after_cost << endl; return 0; }