首页 > 代码库 > hdu4081 Qin Shi Huang's National Road System 次小生成树
hdu4081 Qin Shi Huang's National Road System 次小生成树
先发发牢骚：图论500题上说这题是最小生成树+DFS，网上搜题解也有人这么做。但是其实就是次小生成树。次小生成树完全当模版题。其中有一个小细节没注意，导致我几个小时一直在找错。有了模版要会用模版，然后慢慢融会贯通。我要走的路还长着啊。
讲讲次小生成树的思想吧。首先，在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，用过为0int 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\n",rat); } return 0;}
hdu4081 Qin Shi Huang's National Road System 次小生成树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。