### Brief description:

。。略）。。。

### Analysis:

。。讀題壓力巨大。。。。但幾乎就是裸的次小生成樹。

。。不過是搞出 s[][] 之後用 checkMax 取代 checkMin。。。另外題目里說和 0 號結點相連的邊保證不會發生故障。特判一下。。。。

（。。。這都能寫不出實在是感人肺腑！。。）

const int N = 1009, M = N * 2; DB w[N][N], _s[N][N], s[N][N]; bool inMST[N][N]; int hd[N], suc[M], to[M]; int n, m; DB mst; void add_edgee(int a, int b){ suc[m] = hd[a], to[m] = b, hd[a] = m++; suc[m] = hd[b], to[m] = a, hd[b] = m++; inMST[a][b] = inMST[b][a] = 1; _s[a][b] = _s[b][a] = OO; } void Prim(){ static DB d[N]; static int c[N], pre[N]; RST(c); fill(d, d+n, OO); d[0] = 0; mst = 0, m = 2; DO(n){ int u = 0; while (c[u]) ++u; FOR(i, u+1, n) if (!c[i] && d[i] < d[u]) u = i; if (u) add_edgee(pre[u], u); mst += d[u], c[u] = 1; REP(v, n) if (!c[v] && d[v] > w[u][v]) d[v] = w[u][v], pre[v] = u; } } #define v to[i] int sta[N], top; void dfs(int r, int u, int p){ REP_G(i, u) if (v != p){ dfs(r, v, u); checkMin(_s[r][u], _s[r][v]); } } void dfs(int u, int p){ int t = top; sta[top++] = u; REP_G(i, u) if (v != p) dfs(v, u); if (!u) return; FOR(i, t, top) checkMin(s[u][p], _s[sta[i]][p]); s[p][u] = s[u][p]; } int x[N], y[N]; int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out2.txt", "w", stdout); #endif Rush{ int k; RD(n, k); RST(hd, inMST); REP(i, n) RD(x[i], y[i]); REP_2(i, j, n, n) w[i][j] = (i == j ? OO : dist((DB)(x[i]-x[j]), (DB)(y[i]-y[j]))), s[i][j] = OO; CPY(_s, w); Prim(); REP(i, n) dfs(i, i, i); top = 0, dfs(0, 0); DB res = 0; int i; FOR_N(i, 1, n) if (!inMST[0][i]) break; if (i != n) FOR(i, 1, n) FOR(j, i+1, n) if (inMST[i][j]) checkMax(res, s[i][j] - w[i][j]); OT((res+mst)*k); } }

### External link:

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1570178