hdu4081 秦始皇修路（次小生成树）

题目ID：hdu4081 秦始皇修路

题目大意：给你若干个坐标，每个坐标表示一个城市，每个城市有若干个人，现在要修路，即建一个生成树，然后有一个魔法师可以免费造路（不消耗人力），然后秦始皇希望这条免费的路A/B最大，A是这条路连接的两个城市人口和，B是出了这条路以外所有路的总长度。让你输出这个A/B。

思路：这道题数据量不大，可以两重for算出点和点之间的距离，建图。A/B这个式子A不难算，B的话作为分母希望越小越好，但是和分子在一起，最小的B未必是最好的B。所以需要枚举所有的A-B组合，最大的那个就是答案。很自然想到最小生成树，假设最小生成树总长为tmp，免费造的这条边如果是最小生成树中的路，那么ratio=A/(tmp-g[i][j])，g[i][j]就是图上的距离;如果造的路不是最小生成树中的路，那么ratio=A/(tmp-path[i][j]），path表示加入i-j这条边后，会形成一个环，这个环中除了我新加的边以外最长的那个边就是path[i][j]，这个思路和计算最小生成树的想法很像。而判断是否在最小生成树中使用过，就用一个used[][]来表示就可以了。

核心代码：

double prim(int v) {

	int i,j,u;

	double sum,tmp;

	sum=0;

	memset(vis,0,sizeof(vis));

	memset(used,0,sizeof(used));

	memset(path,0,sizeof(path));

	for(i=1; i<=n; i++) {

		dis[i]=g[v][i];

		pre[i]=1;//pre[i]表示 将i点联系到生成树点集里的那个点；

	}

	vis[v]=1;

	for(i=1; i<n; i++) {

		u=v;

		tmp=INF;

		for(j=1; j<=n; j++)

			if(dis[j]<tmp&&vis[j]==0) {

				tmp=dis[j];

				u=j;

									  }

		sum+=tmp;

		vis[u]=1;

		used[u][pre[u]]=used[pre[u]][u]=1;//表示最小生成树中   u和pre[u]是其中的一条路

		for(j=1; j<=n; j++) {

			if(vis[j]&&j!=u)  //j已经在树上 所以path[j][pre[u]]之前已经计算过了（j和pre[u]都在树上了）

				path[u][j]=path[j][u]=max(path[j][pre[u]],dis[u]);//  u-j环 的最大权值=max（u到点集（pre[u]）的距离，j-pre[u]环的最大权值）；

			if(!vis[j]) {

				if(dis[j]>g[u][j]) {

					dis[j]=g[u][j];

					pre[j]=u;//若松弛  则更新

				                   }

			            }

		                    }

	                  }

	return sum;

}

这样处理完可以得到tmp和path[i][j],然后就是

A=max(A,(a[i].peo+a[j].peo)/(tmp-g[i][j]))和

A=max(A,(a[i].peo+a[j].peo)/(tmp-path[i][j]))的区别了

具体看完整代码：

#include <math.h>

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

const double INF=0x3f3f3f3f;

using namespace std;

double dis[1005],path[1005][1005],g[1005][1005];

int n,m,pre[1005],vis[1005],used[1005][1005];

double get(double x1,double y1,double x2,double y2) {

	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));

}

double prim(int v) {

	int i,j,u;

	double sum,tmp;

	sum=0;

	memset(vis,0,sizeof(vis));

	memset(used,0,sizeof(used));

	memset(path,0,sizeof(path));

	for(i=1; i<=n; i++) {

		dis[i]=g[v][i];

		pre[i]=1;//pre[i]表示 将i点联系到生成树点集里的那个点；

	}

	vis[v]=1;

	for(i=1; i<n; i++) {

		u=v;

		tmp=INF;

		for(j=1; j<=n; j++)

			if(dis[j]<tmp&&vis[j]==0) {

				tmp=dis[j];

				u=j;

									  }

		sum+=tmp;

		vis[u]=1;

		used[u][pre[u]]=used[pre[u]][u]=1;//表示最小生成树中   u和pre[u]是其中的一条路

		for(j=1; j<=n; j++) {

			if(vis[j]&&j!=u)  //j已经在树上 所以path[j][pre[u]]之前已经计算过了（j和pre[u]都在树上了）

				path[u][j]=path[j][u]=max(path[j][pre[u]],dis[u]);//  u-j环 的最大权值=max（u到点集（pre[u]）的距离，j-pre[u]环的最大权值）；

			if(!vis[j]) {

				if(dis[j]>g[u][j]) {

					dis[j]=g[u][j];

					pre[j]=u;//若松弛  则更新

				                   }

			            }

		                    }

	                  }

	return sum;

}

struct dian {

	double x,y;

	int peo;

} a[1005];

int main() {

	int t;

	scanf("%d",&t);

	while(t--) {

		scanf("%d",&n);

		for(int i=1; i<=n; i++) {

			scanf("%lf%lf%d",&a[i].x,&a[i].y,&a[i].peo);

		}

		for(int i=1; i<=n; i++) {

			for(int j=i+1; j<=n; j++) {

				g[i][j]=g[j][i]=get(a[i].x,a[i].y,a[j].x,a[j].y);

			}

		}

		double tmp=prim(1);

		double A=0;

		for(int i=1; i<=n; i++) {

			for(int j=i+1; j<=n; j++) {

				if(used[i][j]) {//在树上   取消的边就是图上的距离

					A=max(A,(a[i].peo+a[j].peo)/(tmp-g[i][j]));

				} else {//不在树上    取消的边是环中的最大权值

					A=max(A,(a[i].peo+a[j].peo)/(tmp-path[i][j]));

				}

			}

		}

		printf("%.2f\n",A);

	}

}

巴特西

hdu4081 秦始皇修路（次小生成树）

最新文章

热门文章