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
| void build() { int cnt = m; sort(a + 1, a + cnt + 1, cmp); st[++top] = 1; for (int i = 1, u, v, x; i <= cnt; i++) { u = st[top]; v = a[i]; x = lca(u, v); if (x == st[top]) { st[++top] = v; } else { while (top > 1 && dfn[st[top - 1]] >= dfn[x]) { int d = mindist(st[top - 1], st[top]); addEdge(st[top], st[top - 1], d); addEdge(st[top - 1], st[top], d); top--; } if (st[top] != x) { int d = mindist(st[top], x); addEdge(st[top], x, d); addEdge(x, st[top], d); st[top] = x; } st[++top] = v; } } while (top > 1) { int d = mindist(st[top - 1], st[top]); addEdge(st[top], st[top - 1], d); addEdge(st[top - 1], st[top], d); top--; } top = 0; }
|