e
#include
#include
#define LL __int64 using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 1010; const int N = 1010; const int M = 300010; struct node { int x, y; } p[maxn]; struct node1 { int to, next; } f[M]; int pre[N], head[N], flag[N]; int vis[N][N]; double low[N]; double dis[N][N], dp[N][N]; int n, m, num; double sum; void init() { sum = 0; num = 0; memset(flag, 0, sizeof(flag)); memset(vis, 0, sizeof(vis)); memset(head, -1, sizeof(head)); memset(dp, 0, sizeof(dp)); } double Dis(int x0, int y0, int x1, int y1) { return sqrt(1.0*(x0-x1)*(x0-x1) + 1.0*(y0-y1)*(y0-y1)); } void add(int s, int t) { f[num].to = t; f[num].next = head[s]; head[s] = num ++; } void prime() { for(int i = 1; i <= n; i++) { low[i] = dis[1][i]; pre[i] = 1; } flag[1] = 1; for(int i = 1; i < n; i++) { double Min = INF; int v; for(int j = 1; j <= n; j++) { if(!flag[j] && Min > low[j]) { v = j; Min = low[j]; } } sum += Min; vis[pre[v]][v] = vis[v][pre[v]] = 1; add(v, pre[v]); add(pre[v], v); flag[v] = 1; for(int j = 1; j <= n; j++) { if(!flag[j] && low[j] > dis[v][j]) { low[j] = dis[v][j]; pre[j] = v; } } } } double dfs(int cur, int u, int fa) //用cur更新cur点所在的子树和另外子树的最短距离 { double ans = INF; for(int i = head[u]; ~i; i = f[i].next) //沿着生成树的边遍历 { if(f[i].to == fa) continue; double tmp = dfs(cur, f[i].to, u); //用cur更新的以当前边为割边的两个子树最短距离 ans = min(tmp, ans); //以(fa,u)为割边的2个子树的最短距离 dp[u][f[i].to] = dp[f[i].to][u] = min(tmp, dp[u][f[i].to]); } if(cur != fa) //生成树边不更新 ans = min(ans, dis[cur][u]); return ans; } int main() { int T; scanf("%d",&T); while(T--) { init(); scanf("%d %d",&n, &m); for(int i = 1; i <= n; i++) scanf("%d %d",&p[i].x, &p[i].y); for(int i = 1; i <= n; i++) { for(int j = 1; j <= i; j++) { dp[i][j] = dp[j][i] = INF; if(i == j) { dis[i][j] = 0.0; continue; } dis[i][j] = dis[j][i] = Dis(p[i].x, p[i].y, p[j].x, p[j].y); } } prime(); double ans = sum; for(int i = 0; i < n; i++) dfs(i, i, -1); for(int i = 2; i <= n; i++) { for(int j = 2; j < i; j++) { if(!vis[i][j]) continue; ans = max(ans, sum-dis[i][j]+dp[i][j]); } } printf("%.2lf\n",ans*m); } return 0; }
|