先发发牢骚:图论500题上说这题是最小生成树+DFS,网上搜题解也有人这么做。但是其实就是次小生成树。次小生成树完全当模版题。其中有一个小细节没注意,导致我几个小时一直在找错。有了模版要会用模版,然后慢慢融会贯通。我要走的路还长着啊。

  这里有两个次小生成树的模版: http://www.cnblogs.com/Potato-lover/p/3949996.html

  此题的解题思想:在prim算法中做一些改变,求出任意两点(u,v)路径之间的最大权值,并记录,记为maxe[u][v]。运行一遍prim算法。枚举每一条边,如果该边是属于最小生成树的边,则ratio=(value(u) +value(v) ) /( ans-map[u][v] ),其中ans是最小生成树的权值之和。否则,ratio=(value(u) +value(v) ) /( ans-maxe[u][v] )。更新ratio的值,取最大值。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int N=,INF=0x3f3f3f3f;
int pre[N];
double dist[N],Map[N][N],maxe[N][N];
//向外延伸的最短边长,记录图信息,最长边
bool vis[N];//1表示点已经在树的,0表示点在树外
bool f[N][N];//存在边为1,用过为0
int n;
double Prim()
{
int i,j,k;
double Min,ans=;
memset(vis,,sizeof(vis));
memset(f,,sizeof(f));
memset(maxe,,sizeof(maxe));
for(i=;i<=n;i++)
{
dist[i]=Map[][i];
pre[i]=;
}
dist[]=;
vis[]=;
pre[]=;
for(i=;i<n;i++)
{
Min=INF;
k=;
for(j=;j<=n;j++)
{
if(!vis[j]&&dist[j]<Min)
{
Min=dist[j];
k=j;
}
}
//if(Min==INF) return -1;//G不连通
vis[k]=;
ans+=Min;
f[pre[k]][k] = f[k][pre[k]]=;
for(j=;j<=n;j++)
{
if(vis[j]&&j!=k) maxe[k][j]=maxe[j][k]=max(maxe[j][pre[k]],dist[k]);
if(!vis[j]&&dist[j]>Map[k][j])
{
dist[j]=Map[k][j];
pre[j]=k;
}
}
}
return ans;
}
struct node
{
double x,y,w;
}nd[N];
double Dis(double x,double y,double a,double b)
{
return sqrt((a-x)*(a-x)+(b-y)*(b-y));
}
int main()
{
//freopen("test.txt","r",stdin);
int cas,i,j;
scanf("%d",&cas);
while(cas--)
{
scanf("%d",&n);
for(i=;i<=n;i++)
Map[i][i]=;
for(i=;i<=n;i++)
scanf("%lf%lf%lf",&nd[i].x,&nd[i].y,&nd[i].w);
for(i=;i<=n;i++)
for(j=;j<i;j++)
Map[i][j]=Map[j][i]=Dis(nd[i].x,nd[i].y,nd[j].x,nd[j].y);
double ans=Prim(), rat=-;
for(i=;i<=n;i++)
{
for(j=;j<=n;j++)if(i!=j)
{
if(!f[i][j])
rat=max(rat,1.0*(nd[i].w+ nd[j].w)/(ans-maxe[i][j])) ;
else
rat=max(rat,1.0*(nd[i].w+ nd[j].w)/(ans-Map[i][j]));
}
}
printf("%0.2f\n",rat);
}
return ;
}
05-11 16:14
查看更多