ACM/ICPC 2011 北京现场赛 Qin Shi Huang’s National Road Syst.
类似于图论的次小生成树。现场赛过程中，在 WH 的提示下，Wideas 敲的这题。赛后 WH 回忆到，比赛时他想起暑假的时候郭炜说：“你们一定要懂次小生成树啊！”结果就想出了这题……
首先生成图的最小生成树，然后，枚举任意两点 u, v: 如果边 (u, v) 就在最小生成树里，那么就算一下把 (u, v) 当成 magic road 时，［人口 / 其余路径长度］的值（即 A / B 的值）；如果边 (u, v) 不在最小生成树里，那么此时如果连接 u 和 v, 就会形成一个环，在环上找到除 (u, v) 外最大的一条边，删除之，再以 (u, v) 为 magic road, 计算 A / B 的值。记录下每次计算出来的值中的最大值，输出之。
我是用 Prim 写的最小生成树，因为这题是一个完全图，边数有点多。然后，我使用了一个二维数组来记录，最小生成树中，路径 u → v 上最长的边有多长。方法是每添加一个新顶点的时候，就判断所有已经添加到最小生成树中的顶点，到新添加的顶点的路径上最长的边的长度。具体内容在我的源代码的 82 到 89 行中。
源代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 | #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <cmath> using namespace std; const int N = 1000; struct edge_t { int u, v; inline edge_t() { } inline edge_t(int u, int v) : u(u), v(v) { } }; double graph[N][N], max_edge[N][N]; int n, population[N], posx[N], posy[N]; class length_greater { public: inline bool operator()(const edge_t &a, const edge_t &b) { return graph[a.u][a.v] > graph[b.u][b.v]; } }; inline void init_and_input() { memset(max_edge, 0, sizeof max_edge); memset(graph, 0, sizeof graph); scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d %d %d", posx + i, posy + i, population + i); for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { int dx = posx[j] - posx[i]; int dy = posy[j] - posy[i]; graph[i][j] = graph[j][i] = sqrt((double)(dx * dx + dy * dy)); } } } inline double less_prim() { priority_queue<edge_t, vector<edge_t>, length_greater> edges; vector<bool> intree(n, false); int last_node = 0; double result = 0; for (int i = 1; i < n; ++i) { intree[last_node] = true; // For each edge from last_node. for (int j = 0; j < n; ++j) if (!intree[j]) edges.push(edge_t(last_node, j)); // Get max valid edge. edge_t edge; do { edge = edges.top(); edges.pop(); } while (intree[edge.u] && intree[edge.v]); double current_length = graph[edge.u][edge.v]; result += current_length; int intree_node, newly_node; if (intree[edge.u]) { intree_node = edge.u; newly_node = edge.v; } else { intree_node = edge.v; newly_node = edge.u; } for (int j = 0; j < n; ++j) { if (intree[j]) { double current_max = max(current_length, max_edge[j][intree_node]); max_edge[j][newly_node] = max_edge[newly_node][j] = current_max; } } last_node = newly_node; } return result; } int main() { // freopen("input.txt", "r", stdin); int T; scanf("%d", &T); while (T--) { init_and_input(); double mst = less_prim(); double max_ratio = 0.0f; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (i == j) continue; int pop = population[i] + population[j]; double non_magic = mst - max_edge[i][j]; double ratio = (double)pop / non_magic; max_ratio = max_ratio > ratio ? max_ratio : ratio; } } printf("%0.2lf\n", max_ratio); } return 0; } |
