最小生成树的练习题。
对应 OJ 的传送门。
《高手训练》解题报告集合:信息学奥赛一本通·高手训练。
与最小生成树相关的更多图论知识:
最小生成树
我们定义无向连通图的 最小生成树 (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; }
This is a topic that’s near to my heart… Cheers!
Exactly where are your contact details though?