秦始皇修路（最小生成树+LCA）

时间：2022-07-08 12:55:53
【问题描述】
 
　　秦朝有N个城市，需要修建一些道路使得任意两个城市之间都可以相互连通。道士徐福生称他可以用法术修路，不花钱，也不用劳动力，但只能修一条，因此需要慎重选择用法术修建哪一条路。


　　秦始皇不仅希望他道路总长度B尽量短（这样可以节省劳力），还希望法术连接的两个城市人口之和A尽量大，因此下令寻找一个使A/B最大的方案。你的任务就是找到这个方案。 


　　注意，并不是任意两个城市都可以修建道路，这个信息在输入中给出。 
 
【输入格式】
 
　　第一行为整数：N,M，分别表示城市数量（编号为1..N）和可选修的道路数量；
　　接下来的一行包含N个整数，第i个整数表示城市i的人口数量。
　　接下来的M行，每行3个整数x,y,cost，表示城市x和城市y之间可以修建一条路，修这条路的花费为cost。
 
【输出格式】
 
　　输出A/B的最大值，四舍五入保留4位小数。
 
【输入样例】
 
6 8
8 7 3 5 9 6
1 2 4
2 3 3
2 4 2
1 5 1
5 6 3
3 5 4
6 2 5
1 6 4


 
【输出样例】
 
1.6667 
 
【数据范围】
 
3<=N<=100000
N<=M<=300000

每个城市的人口数量不超过：2 000 000 000


cqyz的题库这题有点不同，《算法竞赛训练指南》上的题目是多组数据，每组都比较小；到了这改了一下，一组数据，规模很大....无非是顺便练一下LCA


分析：

1.题目大意：让你选一些边，把整个图连通，然后从中选一条边，这边连接的两个点的人口和为分子，总路径长度减去这条路做分母，然后求分子除以分母最大是多少；注意，此处只要这个比值最大，不要求路径最短或者人最多；

2.要让这个比值尽量大，分子是人口不好操作，分母要尽量小却可行，也就是边的长度和要尽量小，便自然想到最小生成树；

3.生成最小生成树之后，接下来只需要枚举每条边（包括生成树里和不在生成树里的），设u，v为这条边连接的两个点，求出最小生成树上两点间的最大边，用这两个点的人口和/(总路径长度-这条最大边的长度），答案取最大值即可。

4.如何实现？？？套用LCA模板，利用2进制，维护maxE和fa数组。这个不会的话需要巩固一下LCA。


细节：

1.为什么求出两点间最大边是对的？

枚举到一条边（u，v）时，最小生成树中u，v已径连通，如果加入这条边就形成圈。因为这条加入的边是免费的，所以相当于这条边的长度为0，可以扔掉原来圈里的的一条边，u，v和其他点仍然连通。因为u，v点的人口是确定的，所以要找一条最大的边扔掉使得比值最大。

2.为什么所有的边都要枚举，而不是只枚举生成树里的或不在生成树里的？

此题和原题不同，原题两个点间可任意连接，于是直接枚举点与点的最大边，两个for即可。

注意读题，此题只能连接给定的边。此处枚举边，实质是在枚举点，只不过是在枚举可以直接连接的点对，因为不像原题任意两个点都可以连，所以下面的代码可以看见枚举边时，枚举到的这条边长度根本没有用到。之所以所有边都枚举就是不放过一个可以连的点对。


注：Ufs_表示这是并查集用的，Tree_表示这是生成树上用的。

#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

typedef long long LL;
typedef double DB;
const LL maxn=100005;
const LL maxm=300005;

LL n,m,np=0,MAXDEP,people[maxn],last[maxn],Tree_fa[maxn][20],Tree_maxE[maxn][20],Tree_dep[maxn],two[25];
LL Ufs_fa[maxn],Ufs_vis[maxm];

struct data{LL u,v,w;}Ufs_E[maxm];
struct edge{LL to,w,pre;}Tree_E[maxn*2];//生成树总共n-1条边 

inline bool cmp(data a,data b) {return a.w<b.w;}

char c;
inline void qkscanf(LL &x)
{
	for(c=getchar();c<'0'||c>'9';c=getchar());
	for(x=0;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';
}

inline void addedge(LL u,LL v,LL w)
{
	Tree_E[++np]=(edge){v,w,last[u]};
	last[u]=np;
}

inline LL Find(LL x) {return Ufs_fa[x]==x?x:Ufs_fa[x]=Find(Ufs_fa[x]);}

inline void Merge(LL x,LL y) {Ufs_fa[Find(x)]=Find(y);}

LL Kruscal()
{
	sort(Ufs_E+1,Ufs_E+1+m,cmp);
	for(LL i=1;i<=n;i++) Ufs_fa[i]=i;
	
	LL sum=0;
	LL cnt=0,u,v,w;
	for(LL i=1;i<=m;i++)
	{
		u=Ufs_E[i].u,v=Ufs_E[i].v,w=Ufs_E[i].w;
		
		if(Find(u)==Find(v)) continue;
		
		sum+=w;
		Merge(u,v);
		Ufs_vis[i]=1;
		cnt++;
		
		addedge(u,v,w);//加入最小生成树 
		addedge(v,u,w);
		
		
		if(cnt==n-1) break;
	}
	
	return sum;
}

inline void DFS(LL i,LL fa,LL maxE_now,LL dep)
{
	Tree_dep[i]=dep;
	Tree_fa[i][0]=fa;
	Tree_maxE[i][0]=maxE_now;
	
	for(LL p=1;p<=MAXDEP;p++)
	{
		LL j=Tree_fa[i][p-1];
		Tree_fa[i][p]=Tree_fa[j][p-1];
		Tree_maxE[i][p]=max(Tree_maxE[i][p-1],Tree_maxE[j][p-1]); 
	}
	
	for(LL p=last[i];p;p=Tree_E[p].pre)
	{
		LL j=Tree_E[p].to;
		if(j==fa) continue;
		DFS(j,i,Tree_E[p].w,dep+1);
	}
}

inline LL LCA(LL u,LL v)
{
	if(Tree_dep[u]<Tree_dep[v]) swap(u,v);
	
	LL x=Tree_dep[u]-Tree_dep[v];
	
	for(LL i=MAXDEP;i>=0;i--) if(x&two[i]) u=Tree_fa[u][i];
	
	if(u==v) return u;
	
	for(LL i=MAXDEP;i>=0;i--) if(Tree_fa[u][i]!=Tree_fa[v][i])
	{
		u=Tree_fa[u][i];
		v=Tree_fa[v][i];
	}
	
	return Tree_fa[u][0];
}

inline LL ques(LL u,LL lca)
{
	LL ans=-1;
	
	for(LL i=MAXDEP;i>=0;i--)
	{
		if(Tree_dep[Tree_fa[u][i]]>=Tree_dep[lca])
		{
			ans=max(ans,Tree_maxE[u][i]);
			u=Tree_fa[u][i];
		}
	}
	
	return ans;
}

int main()
{
//	freopen("in.txt","r",stdin);

	//input
	qkscanf(n);qkscanf(m);
	LL u,v,w;
	for(LL i=1;i<=n;i++) qkscanf(people[i]);
	
	for(LL i=1;i<=m;i++)
	{
		qkscanf(u);qkscanf(v);qkscanf(w);
		Ufs_E[i]=(data){u,v,w};
	}
	
	//form a tree
	LL sum=Kruscal();
	
	LL i=0,k=1;
	while(k<n*3) two[i++]=k,k*=2;//2的次方，便于调用 
	MAXDEP=i;//最大深度，枚举2的次方时用到 
	
	DFS(1,0,0,1);//生成树上的信息 
	
	//solve question
	DB ans=-1;
	for(LL i=1;i<=m;i++)
	{
		u=Ufs_E[i].u,v=Ufs_E[i].v;//   并没有用到这条边的长度！！！！ 
		LL lca=LCA(u,v);
		LL MAXE=max(ques(u,lca),ques(v,lca));
		DB t=(DB)(people[u]+people[v])/(DB)(sum-MAXE);
		ans=max(ans,t);
	}
	
	//output
	printf("%.4llf",ans);
	
	return 0;
}

标签：

相关文章