题目大意：给n个点，现在要使这n个点连通，并且要求代价最小。现在有2个点之间不能直接连通（除了第一个点），求最小代价。
题目分析：跟这题一样样的，唉，又是原题。。先求mst，然后枚举边，对于生成树上的边替换，用树形dp O(N^2)求出每条生成树边的最小替代边。然后替换后的最大值。
详情请见代码：
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<string>
using namespace std;
const int N = 1005;
const int M = 3000005;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const double PI = acos(-1.0);
typedef __int64 ll;
double dis[N][N];
double dp[N][N];
bool used[N][N];
bool flag[N];
double lowcost[N];
int pre[N],head[N];
struct node
{
int x,y;
}pt[N];
struct nd
{
int to,next;
}e_mst[M];
int n,m,num;
double B;
void build(int s,int e)
{
e_mst[num].to = e;
e_mst[num].next = head[s];
head[s] = num ++;
}
double getdis(int x1,int y1,int x2,int y2)
{
return sqrt((double)(x1 - x2) * (double)(x1 - x2) + (double)(y1 - y2) * (double)(y1 - y2));
}
void prim()
{
B = 0;
int i,j;
memset(flag,false,sizeof(flag));
for(i = 1;i <= n;i ++)
{
lowcost[i] = dis[1][i];
pre[i] = 1;
}
flag[1] = true;
for(i = 1;i < n;i ++)
{
double Min = 100000000.0;
int v;
for(j = 1;j <= n;j ++)
{
if(flag[j] == false && lowcost[j] < Min)
{
Min = lowcost[j];
v = j;
}
}
B += Min;
used[pre[v]][v] = used[v][pre[v]] = true;
build(v,pre[v]);
build(pre[v],v);
flag[v] = true;
for(j = 1;j <= n;j ++)
{
if(flag[j] == false && lowcost[j] > dis[v][j])
{
lowcost[j] = dis[v][j];
pre[j] = v;
}
}
}
}
double dfs(int cur,int u,int fa)
{
double ret = inf;
for(int i = head[u];~i;i = e_mst[i].next)
{
if(e_mst[i].to == fa)
continue;
double tmp = dfs(cur,e_mst[i].to,u);
ret = min(tmp,ret);
dp[u][e_mst[i].to] = dp[e_mst[i].to][u] = min(tmp,dp[u][e_mst[i].to]);
}
if(cur != fa)
ret = min(ret,dis[cur][u]);
return ret;
}
int main()
{
int t,i,j;
scanf("%d",&t);
while(t --)
{
scanf("%d%d",&n,&m);
for(i = 1;i <= n;i ++)
scanf("%d%d",&pt[i].x,&pt[i].y);
for(i = 1;i <= n;i ++)
for(j = 1;j <= i;j ++)
{
dp[i][j] = dp[j][i] = inf;
if(i == j)
dis[i][j] = 0;
else
dis[i][j] = dis[j][i] = getdis(pt[i].x,pt[i].y,pt[j].x,pt[j].y);
}
memset(used,false,sizeof(used));
memset(head,-1,sizeof(head));
num = 0;
prim();
double ans = B;
for(i = 0;i < n;i ++)
dfs(i,i,-1);
for(i = 2;i <= n;i ++)
{
for(j = 2;j < i;j ++)
{
if(used[i][j] == true)
{
ans = max(ans,B-dis[i][j]+dp[i][j]);
}
}
}
printf("%.2lf
",ans*m);
}
return 0;
}
//718MS 17100K