先求最小生成树

再遍历每一对顶点,如果该顶点之间的边属于最小生成树,则剪掉这对顶点在最小生成树里的最长路径

否则直接剪掉连接这对顶点的边~

用prim算法求最小生成树最长路径的模板~

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
const int maxn=;
const int inf=1e9;
double g[maxn][maxn],d[maxn],w[maxn];
int visit[maxn],N,S,P,pre[maxn];
double len[maxn][maxn];//表示点i,j在最小生成树上的最长路径
double c[maxn][maxn];
void init () {
for (int i=;i<maxn;i++)
for (int j=;j<maxn;j++)
g[i][j]=inf,c[i][j]=,len[i][j]=;
}
double prim (int s) {
fill (d,d+maxn,inf);
fill (visit,visit+maxn,);
for (int i=;i<=N;i++) pre[i]=i;
d[s]=;
double ans=;
for (int i=;i<=N;i++) {
int u=-,min=inf;
for (int j=;j<=N;j++)
if (!visit[j]&&d[j]<min) {
u=j;
min=d[j];
}
if (u==-) return -;
visit[u]=;
ans+=d[u];
if (pre[u]!=u) c[u][pre[u]]=c[pre[u]][u]=;
for (int v=;v<=N;v++)
if (!visit[v]&&g[u][v]!=inf&&g[u][v]<d[v]) {
d[v]=g[u][v];
pre[v]=u;
}
for (int v=;v<=N;v++)
if (visit[v]&&u!=v) len[u][v]=len[v][u]=max(len[pre[u]][v],d[u]);
}
return ans;
}
struct node {
double x,y;
}Node[maxn];
int main () {
int T;
scanf ("%d",&T);
while (T--) {
scanf("%d",&N);
for (int i=;i<=N;i++) scanf ("%lf %lf %lf",&Node[i].x,&Node[i].y,&w[i]);
init ();
for (int i=;i<=N;i++)
for (int j=i+;j<=N;j++)
g[i][j]=g[j][i]=sqrt((Node[i].x-Node[j].x)*(Node[i].x-Node[j].x)+(Node[i].y-Node[j].y)*(Node[i].y-Node[j].y));
double mst=prim();
double Max=;
for (int i=;i<=N;i++)
for (int j=i+;j<=N;j++)
if (!c[i][j]) Max=max(Max,(w[i]+w[j])/(mst-len[i][j]));
else Max=max(Max,(w[i]+w[j])/(mst-g[i][j]));
printf ("%.2f\n",Max);
}
return ;
}
05-11 16:14
查看更多