最小生成树的练习题。
对应 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;
}
近期评论