本文共 2309 字，大约阅读时间需要 7 分钟。
题目大意：给n个点，现在要使这n个点连通，并且要求代价最小。现在有2个点之间不能直接连通（除了第一个点），求最小代价。
题目分析：先求mst，然后枚举边，对于生成树上的边替换，用树形dp O(N^2)求出每条生成树边的最小替代边。然后替换后的最大值。
详情请见代码：
#include #include #include #include #include #include #include #include #include #include #include #include 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\n",ans*m); } return 0;}//718MS 17100K
转载地址：http://bfvml.baihongyu.com/