先发发牢骚：图论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=1010,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=0; memset(vis,0,sizeof(vis)); memset(f,0,sizeof(f)); memset(maxe,0,sizeof(maxe)); for(i=2;i<=n;i++) { dist[i]=Map[1][i]; pre[i]=1; } dist[1]=0; vis[1]=1; pre[1]=0; for(i=1;i<n;i++) { Min=INF; k=0; for(j=1;j<=n;j++) { if(!vis[j]&&dist[j]<Min) { Min=dist[j]; k=j; } } //if(Min==INF) return -1;//G不连通 vis[k]=1; ans+=Min; f[pre[k]][k] = f[k][pre[k]]=1; for(j=1;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=1;i<=n;i++) Map[i][i]=0; for(i=1;i<=n;i++) scanf("%lf%lf%lf",&nd[i].x,&nd[i].y,&nd[i].w); for(i=1;i<=n;i++) for(j=1;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=-1; for(i=1;i<=n;i++) { for(j=1;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 ",rat); } return 0; }