《高手训练》解题报告 3.1 最小生成树

最小生成树的练习题。

对应 OJ 的传送门

《高手训练》解题报告集合:信息学奥赛一本通·高手训练

与最小生成树相关的更多图论知识:

1. 最小生成树《高手训练》解题报告 3.1 最小生成树

最小生成树

我们定义无向连通图的 最小生成树 (Minimum Spanning Tree,MST)为边权和最小的生成树。

注意:只有连通图才有生成树(最小生成树),而对于非连通图,只存在生成森林(最小生成森林)。

构造完全图 tree

时空限制:\(1\texttt{s},256\texttt{MiB}\)。

题目描述

对于完全图 \(G\),若有且仅有一棵最小生成树为 \(T\),则称完全图 \(G\) 是树 \(T\) 的扩展出的。给你一棵树 \(T\),找出 \(T\) 能扩展出的边权和最小的完全图 \(G\)。求最小的图 \(G\) 的边权和。

数据范围

对于 \(100\%\) 的数据,\(n\leq 10^5\),\(1\leq D_i\leq 10^5\)。

题解

考虑求解最小生成树时 \(\texttt{Kruskal}\) 每次加边的过程,不难发现设该边为 \(\left<u,v\right>\),边权为 \(\omega\),那么对答案的贡献为 \((\text{size}_u\times\text{size}_v-1)(\omega+1)\)。

\(\texttt{Kruskal}\) 直接求解即可,时间复杂度为 \(\Theta(n\log_2n)\)。

#include<cstdio>
#include<algorithm>
using std::sort;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXN=100000+5;

struct Edge{
	int f,t,len;
	inline Edge(void){
		f=t=len=0;
		return;
	}
	inline Edge(reg int a,reg int b,reg int c){
		f=a,t=b,len=c;
		return;
	}
	inline void Read(void){
		f=read(),t=read(),len=read();
		return;
	}
	inline bool operator<(const Edge& a)const{
		return len<a.len;
	}
};

struct UnionFind{
	int ID[MAXN],size[MAXN];
	inline void Init(reg int n){
		reg int i;
		for(i=1;i<=n;++i)
			ID[i]=i,size[i]=1;
		return;
	}
	inline int find(reg int x){
		if(x==ID[x])
			return x;
		else
			return ID[x]=find(ID[x]);
	}
	inline void merge(reg int a,reg int b){
		reg int ra=find(a),rb=find(b);
		if(ra!=rb){
			ID[rb]=ra;
			size[ra]+=size[rb];
		}
		return;
	}
	inline bool search(reg int a,reg int b){
		return find(a)==find(b);
	}
};

int n;
int cnt;
Edge E[MAXN];
UnionFind S;

int main(void){
	reg int i;
	reg ll ans=0;
	n=read();
	for(i=1;i<n;++i)
		E[i].Read();
	sort(E+1,E+n);
	S.Init(n);
	for(i=1;i<n&&cnt<n-1;++i)
		if(!S.search(E[i].f,E[i].t)){
			++cnt;
			ans+=(ll)(E[i].len+1)*((ll)S.size[S.find(E[i].f)]*S.size[S.find(E[i].t)]-1);
			S.merge(E[i].f,E[i].t);
		}
	for(i=1;i<n;++i)
		ans+=E[i].len;
	printf("%lld\n",ans);
	return 0;
}

最小花费

时空限制:\(1\texttt{s},256\texttt{MiB}\)。

题目描述

有 \(n\) 个未知数,每个数都是 \(0\) 或 \(1\),这些未知数已经按 \(1\) 到 \(n\) 编好了序。询问第 \(i\) 个未知数到第 \(j\) 个未知数的和的奇偶性,需要付出一定费用。给出询问每个区间 \([i,j]\) 的和的奇偶性的代价。你需要设计一个询问的方案,使得你能推断出这 \(n\) 个每个数的值,并使代价的总和最小。

数据范围

对于 \(100\%\) 的数据,\(2<n\leq 10^3\),\(1\leq i\leq j\leq n\),\(0\leq c_{i,j}\leq 10^9\)。

题解

我们每次询问可以得到 \(\text{sum}_j-\text{sum}_{i-1}\) 的奇偶性,那么不难发现,只要我们把 \(0\sim n\) 个点通过询问连接起来,即可得到每个点的值的奇偶性。把整个图连成一个连通块的过程所需代价就是最小生成树的权值和,用 \(\texttt{Prim}\) 算法求解最小生成树即可,时间复杂度为 \(\Theta(n^2)\)。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXN=2e3+5;
const int inf=0x3f3f3f3f;

int n;
int g[MAXN][MAXN];
bool vis[MAXN];
int dis[MAXN];

int main(void){
	n=read();
	for(reg int i=1;i<=n;++i)
		for(reg int j=i;j<=n;++j){
			static int x;
			x=read();
			g[i-1][j]=g[j][i-1]=x;
		}
	reg ll ans=0;
	dis[0]=0;
	for(reg int i=1;i<=n;++i)
		dis[i]=g[0][i];
	for(reg int i=1;i<=n;++i){
		reg int Min=inf,pos=0;
		for(reg int j=1;j<=n;++j)
			if(!vis[j]&&dis[j]<Min)
				Min=dis[j],pos=j;
		vis[pos]=true;
		ans+=Min;
		for(reg int j=1;j<=n;++j)
			if(!vis[j]&&dis[j]>g[pos][j])
				dis[j]=g[pos][j];
	}
	printf("%lld\n",ans);
	return 0;
}

汉堡店 loser

时空限制:\(1\texttt{s},256\texttt{MiB}\)。

题目描述

市中心有 \(N\) 家汉堡店,每两家汉堡店间都有一条双向道路。由于汉堡店间的路太过于复杂,决定只保留其中 \(N−1\) 条道路(必须保证每两家汉堡店间都连通),其它道路都无视掉。

经过一段时间的考虑,准备吃光两家汉堡店(两家汉堡店在新图中必须有边)。

假设吃光了 \(a,b\) 两家的汉堡,那么就会得到 \(\left\lfloor\frac{A}{B}\right\rfloor\) 的愉悦度,其中:

  • \(A=P_a+P_b\)(\(P_i\) 是第 \(i\) 家汉堡店的美味度);
  • \(B=\) 除了道路 \((a,b)\) 外,新图中所有道路的权值之和(道路的权值为两家汉堡店之间的欧几里德距离)。

想知道他最多得到的愉悦度是多少。

数据范围

对于 \(100\%\) 数据,满足 \(2<N\leq 10^3\),\(0\leq X,Y\leq 10^3\),\(0<p<10^4\)。

题解

考虑枚举 \(a,b\),则生成树有两种情况:

  • \((a,b)\) 在生成树中,\(B\) 为最小生成树的权值减去 \((a,b)\) 的权值;
  • \((a,b)\) 不在生成树中,\(B\) 为最小生成树的权值减去 \(a,b\) 间的最大边权。

如果 \((a,b)\) 在生成树中,那么 \(a,b\) 间的路径显然只有 \((a,b)\) 一条,此时显然等于 \(a,b\) 间的最大边权。第一种情况可以并入第二种情况,求得最小生成树后每次直接倍增求解最小生成树上 \(a,b\) 间的最大边权即可,时间复杂度为 \(\Theta(n^2\log_2n^2)\)。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXN=1e3+5;
const int MAXLOG2N=10+1;
const int MAXE=MAXN*(MAXN-1)/2;

struct Node{
	int x,y,p;
	inline Node(reg int x=0,reg int y=0,reg int p=0):x(x),y(y),p(p){
		return;
	}
};

inline double sqr(reg double x){
	return x*x;
}

inline double getDis(const Node& a,const Node& b){
	return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}

struct Edge{
	int u,v;
	double w;
	inline Edge(reg int u=0,reg int v=0,reg double w=0.0):u(u),v(v),w(w){
		return;
	}
	inline bool operator<(const Edge& a)const{
		return w<a.w;
	}
};

namespace UnionFind{
	int fa[MAXN];
	inline void Init(reg int n){
		for(reg int i=1;i<=n;++i)
			fa[i]=i;
		return;
	}
	inline int find(reg int x){
		if(x==fa[x])
			return x;
		else
			return fa[x]=find(fa[x]);
	}
	inline void merge(reg int a,reg int b){
		reg int ra=find(a),rb=find(b);
		if(ra!=rb)
			fa[rb]=ra;
		return;
	}
	inline bool search(reg int a,reg int b){
		return find(a)==find(b);
	}
}

int n;
Node a[MAXN];
Edge E[MAXE];
int cnt,head[MAXN],to[MAXN<<1],Next[MAXN<<1];
double w[MAXN<<1];

inline void Add_Edge(reg int u,reg int v,reg double len){
	Next[++cnt]=head[u];
	to[cnt]=v;
	w[cnt]=len;
	head[u]=cnt;
	return;
}

int fa[MAXN][MAXLOG2N],dep[MAXN];
double Max[MAXN][MAXLOG2N];

inline void dfs(reg int u,reg int father){
	fa[u][0]=father;
	dep[u]=dep[father]+1;
	for(reg int i=1;i<MAXLOG2N;++i){
		fa[u][i]=fa[fa[u][i-1]][i-1];
		Max[u][i]=max(Max[u][i-1],Max[fa[u][i-1]][i-1]);
	}
	for(reg int i=head[u];i;i=Next[i]){
		reg int v=to[i];
		if(v!=father){
			Max[v][0]=w[i];
			dfs(v,u);
		}
	}
	return;
}

inline double getMax(int x,int y){
	double res=0.0;
	if(dep[x]>dep[y])
		swap(x,y);
	for(reg int i=MAXLOG2N-1;i>=0;--i)
		if(dep[fa[y][i]]>=dep[x]){
			res=max(res,Max[y][i]);
			y=fa[y][i];
		}
	if(x==y)
		return res;
	for(reg int i=MAXLOG2N-1;i>=0;--i)
		if(fa[x][i]!=fa[y][i]){
			res=max(res,max(Max[x][i],Max[y][i]));
			x=fa[x][i],y=fa[y][i];
		}
	return max(res,max(Max[x][0],Max[y][0]));
}

int main(void){
	n=read();
	for(reg int i=1;i<=n;++i){
		static int x,y,p;
		x=read(),y=read(),p=read();
		a[i]=Node(x,y,p);
	}
	reg int tot=0;
	for(reg int i=1;i<=n;++i)
		for(reg int j=i+1;j<=n;++j)
			E[++tot]=Edge(i,j,getDis(a[i],a[j]));
	reg int cnt=n;
	reg double sum=0;
	UnionFind::Init(n);
	sort(E+1,E+tot+1);
	for(reg int i=1;i<=tot&&cnt>1;++i)
		if(!UnionFind::search(E[i].u,E[i].v)){
			--cnt;
			sum+=E[i].w;
			Add_Edge(E[i].u,E[i].v,E[i].w);
			Add_Edge(E[i].v,E[i].u,E[i].w);
			UnionFind::merge(E[i].u,E[i].v);
		}
	dfs(1,0);
	double ans=0.0;
	for(reg int i=1;i<=n;++i)
		for(reg int j=i+1;j<=n;++j)
			ans=max(ans,1.0*(a[i].p+a[j].p)/(sum-getMax(i,j)));
	printf("%.2lf\n",ans);
	return 0;
}

生成树 road

时空限制:\(1\texttt{s}/128\texttt{MiB}\)。

题目描述

给定一张 \(N\) 个点 \(M\) 条边的无向图,求图中所有生成树边权最大公约数的最小公倍数。

数据范围

对于 \(100\%\) 的数据,\(N\leq 10^3\),\(M\leq 10^5\),\(d_i\leq 2^{15}-1\),\(\text{ans}\leq 2^{64}-1\)。

题解

对于某一颗生成树而言,在求最大公因数的时候,边权的各个质因子互不干扰,所以可以分开来考虑。

考虑每个质因子 \(p_i\) 对答案的贡献,则对最大公因数的贡献为 \(\min\{p_i^{c_i}\}\),最小公倍数为 \(\max\{\min\{p_i^{c_i}\}\}\),由于底数相等,所以我们只要记录指数,对各个质因子求一遍最大生成树,最小边权即为它的贡献。

时间复杂度为 \(\Theta(m\log_2m+\log_2m(n\omega(n)\alpha(n)))\)。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXN=1e3+5;
const int MAXM=1e5+5;
const int MAXSIZE=(1<<15)+5;

struct Edge{
	int s,t,d;
	inline Edge(reg int s=0,reg int t=0,reg int d=0):s(s),t(t),d(d){
		return;
	}
	inline bool operator<(const Edge& a)const{
		return d>a.d;
	}
};

namespace UnionFind{
	int fa[MAXN],dep[MAXN];
	inline void Init(reg int n){
		for(reg int i=1;i<=n;++i)
			fa[i]=i,dep[i]=1;
		return;
	}
	inline int find(reg int x){
		if(x==fa[x])
			return x;
		else
			return fa[x]=find(fa[x]);
	}
	inline void merge(reg int a,reg int b){
		reg int ra=find(a),rb=find(b);
		if(ra==rb)
			return;
		if(dep[ra]<dep[rb])
			fa[ra]=rb;
		else if(dep[ra]>dep[rb])
			fa[rb]=ra;
		else
			fa[rb]=ra,++dep[ra];
		return;
	}
	inline bool search(reg int a,reg int b){
		return find(a)==find(b);
	}
}

bool vis[MAXSIZE];
int tot,prime[MAXSIZE];
int rnk[MAXSIZE];
int from[MAXSIZE];

inline void Init(reg int n){
	from[1]=1;
	for(reg int i=2;i<=n;++i){
		if(!vis[i]){
			prime[++tot]=i;
			rnk[i]=tot;
			from[i]=i;
		}
		for(reg int j=1;j<=tot&&i*prime[j]<=n;++j){
			vis[i*prime[j]]=true,from[i*prime[j]]=prime[j];
			if(i%prime[j]==0)
				break;
		}
	}
	return;
}

inline ll fpow(reg ll x,reg ll exp){
	reg ll res=1;
	while(exp){
		if(exp&1)
			res=res*x;
		x=x*x;
		exp>>=1;
	}
	return res;
}

int n,m;
Edge E[MAXM];
vector<Edge> V[MAXSIZE];

int main(void){
	Init((1<<15)-1);
	n=read(),m=read();
	for(reg int i=1;i<=m;++i){
		static int s,t,d;
		s=read(),t=read(),d=read();
		E[i]=Edge(s,t,d);
	}
	int Maxptr=0;
	for(reg int i=1;i<=m;++i){
		reg int tmp=E[i].d;
		while(from[tmp]>1){
			reg int las=from[tmp],cnt=0;
			while(tmp%las==0){
				++cnt;
				tmp/=las;
			}
			V[rnk[las]].push_back(Edge(E[i].s,E[i].t,cnt));
			Maxptr=max(Maxptr,rnk[las]);
		}
	}
	reg ll ans=1;
	for(reg int i=1;i<=Maxptr;++i){
		reg int cnt=n,Min=0;
		UnionFind::Init(n);
		sort(V[i].begin(),V[i].end());
		for(reg int j=0,siz=V[i].size();j<siz&&cnt>1;++j){
			static Edge E;
			E=V[i][j];
			if(!UnionFind::search(E.s,E.t)){
				--cnt;
				Min=E.d;
				UnionFind::merge(E.s,E.t);
			}
		}
		if(cnt==1)
			ans=ans*fpow(prime[i],Min);
	}
	printf("%lld\n",ans);
	return 0;
}

地壳运动 mst

时空限制:\(5\texttt{s}/128\texttt{MiB}\)。

题目描述

城市中建立了 \(N\) 个应急避难所以躲避灾害,这些避难所从 \(1\sim N\) 编号。此外有 \(M\) 条道路连接这些避难所,所有避难所间均可通过这 \(M\) 条道路直接或间接到达。路可以由若干个平行于 \(x\) 或 \(y\) 坐标轴的线段组成,所以避难所 \(x_i\) 和 \(y_i\) 之间的道路可以用 \((u_i,v_i)\) 来表示,道路的长度为 \(u_i+v_i\)。

由于地壳运动会导致地面拉伸或收缩,可用两个实数 \(k_1,k_2\) 描述城市的伸缩程度,此时某条道路的实际长度变为 \(u_i\times k_1+v_i\times k_2\)。

有若干个独立的询问,每次询问给出 \(k_1\) 和 \(k_2\),政府都希望在此地壳运动前提下,以最小的花费维护其中一些道路,使得只用这些被维护的道路仍能使所有避难所间相互连通。因为花费与道路的实际总长成正比,所以你需要对每一次询问求出被维护道路的最短实际总长度。

数据范围

对于 \(100\%\) 的数据,\(N\leq 35\),\(M\leq 2.5\times 10^4\),\(Q\leq 2\times 10^5\),\(1\leq x_i,y_i\leq N\),\(0\leq u_i,v_i\leq 10^6\),\(k_1,k_2>0\)。

题解

考虑求出各个点之间的最短边权之后直接用求最小生成树的 \(\texttt{Prim}\) 算法求解,那么下面考虑怎么求出各个点之间的最短边权。

设 \(x,y\) 之间的最短边权为 \(g_{x,y}\),\(x,y\) 之间边的集合为 \(S_{x,y}\),那么我们有
\[g_{x,y}=\min_{E_i\in S_{x,y}}\{k_1u_i+k_2v_i\}\]

考虑斜率优化,有
\[v_i=-\frac{k_1}{k_2}u_i+\frac{g_{x,y}}{k_2}\]

我们为了后续处理方便高效,可以先按 \(u_i\) 排序,保证横坐标单调递增。

同时,我们可以把询问离线出来,按 \(-\frac{k_1}{k_2}\) 排序,保证斜率单调递增。

我们维护的横坐标、斜率均单调递增,则通过单调队列可以轻松维护,均摊复杂度为 \(\Theta(1)\)。

时间复杂度为 \(\Theta(n^2+m\log_2m+Q\log_2Q)\)。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXN=35+5;
const int MAXM=2.5e4+5;
const int MAXQ=2e5+5;
const double inf=1e40;

struct Node{
	int u,v;
	inline Node(reg int u=0,reg int v=0):u(u),v(v){
		return;
	}
	inline bool operator<(const Node& a)const{
		return u<a.u;
	}
};

struct querys{
	int id;
	double k1,k2;
	inline querys(reg int id=0,reg double k1=0.0,reg double k2=0.0):id(id),k1(k1),k2(k2){
		return;
	}
	inline bool operator<(const querys& a)const{
		return k1*a.k2>k2*a.k1;
	}
};

int n,m,Q;
vector<Node> p[MAXN][MAXN];
int head[MAXN][MAXN],siz[MAXN][MAXN];
vector<Node> con[MAXN][MAXN];
querys q[MAXQ];
double ans[MAXQ];
bool vis[MAXN];
double dis[MAXN],g[MAXN][MAXN];

inline double prim(reg double k1,reg double k2){
	memset(vis,false,sizeof(vis));
	for(reg int i=1;i<=n;++i){
		dis[i]=inf;
		for(reg int j=i+1;j<=n;++j){
			g[i][j]=g[j][i]=inf;
			if(head[i][j]<siz[i][j]){
				int s=siz[i][j];
				while(head[i][j]<s-1&&1.0*(con[i][j][head[i][j]+1].v-con[i][j][head[i][j]].v)/(con[i][j][head[i][j]+1].u-con[i][j][head[i][j]].u)<-k1/k2)
					++head[i][j];
				g[i][j]=g[j][i]=k1*con[i][j][head[i][j]].u+k2*con[i][j][head[i][j]].v;
			}
		}
	}
	reg double sum=0;
	dis[1]=0;
	for(reg int i=1;i<=n;++i){
		reg int pos=0;
		reg double Min=inf;
		for(reg int j=1;j<=n;++j)
			if(!vis[j]&&dis[j]<Min)
				Min=dis[j],pos=j;
		vis[pos]=true;
		sum+=dis[pos];
		for(reg int j=1;j<=n;++j)
			if(!vis[j])
				dis[j]=min(dis[j],g[pos][j]);
	}
	return sum;
}

int main(void){
	n=read(),m=read(),Q=read();
	for(reg int i=1;i<=m;++i){
		static int x,y,u,v;
		x=read(),y=read(),u=read(),v=read();
		if(x==y)
			continue;
		if(x>y)
			swap(x,y);
		p[x][y].push_back(Node(u,v));
	}
	for(reg int i=1;i<=n;++i)
		for(reg int j=i+1;j<=n;++j)
			if(!p[i][j].empty()){
				sort(p[i][j].begin(),p[i][j].end());
				reg int &s=siz[i][j];
				for(reg int k=0,siz=p[i][j].size();k<siz;++k){
					static Node x;
					x=p[i][j][k];
					if(s>0&&con[i][j][s-1].u==x.u){
						if(con[i][j][s-1].v<x.v)
							continue;
						else
							con[i][j].pop_back(),--s;
					}
					while(s>1&&1ll*(con[i][j][s-2].v-con[i][j][s-1].v)*(con[i][j][s-1].u-x.u)>1ll*(con[i][j][s-1].v-x.v)*(con[i][j][s-2].u-con[i][j][s-1].u))
						con[i][j].pop_back(),--s;
					con[i][j].push_back(x),++s;
				}
			}
	for(reg int i=1;i<=Q;++i){
		static double k1,k2;
		scanf("%lf%lf",&k1,&k2);
		q[i]=querys(i,k1,k2);
	}
	sort(q+1,q+Q+1);
	for(reg int i=1;i<=Q;++i)
		ans[q[i].id]=prim(q[i].k1,q[i].k2);
	for(reg int i=1;i<=Q;++i)
		printf("%.3lf\n",ans[i]);
	return 0;
}