题解：洛谷P8207 [THUPC2022 初赛] 最小公倍树

巩固一下最小生成树的Kruskal算法（）

洛谷

---

思路

首先如果我们将完全图的所有边都存下来，最多需要 $(R-L)^2$ 条边，时空复杂度皆到了 $10^{10}$

所以我们选择在存边的部分进行优化

首先对于两个点，它们连边的权值为 $lcm(u,v)$ ，这意味着当 $gcd(u,v)$ 越大，权值越优

因此，对于每一个 $i\in{[1,R]}$，我们枚举它符合在 $[L,R]$ 区间内的倍数存下来

然后套kruskal板子即可

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

ll l,r;
ll par[1000005];

struct edge
{
	ll u,v,w;
};

vector<edge> e;

ll find(ll x)
{
	return par[x]==x?x:par[x]=find(par[x]);
}

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

ll n,m;
ll ans;

void kruskal()
{	
	for(ll i=0;i<e.size();i++)
	{
		ll u=find(e[i].u),v=find(e[i].v);
		
		if(u==v)
		{
			continue;
		}
		
		ans+=e[i].w;
		par[u]=v;
	}
	
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	cin>>l>>r;
	
    for(ll i=l;i<=r;i++)
	{
		par[i]=i;
	}
    for(ll i=1;i<=r;i++)  //存边
	{
        ll v=ceil(l*1.0/i)*i; //不小于L的第一个i的倍数
        for(ll j=v;j<=r;j+=i)
		{
            if(j!=v) //非自环
			{
				e.push_back({v,j,v*j/__gcd(v,j)});
			}
        }
    }
    
    sort(e.begin(),e.end(),cmp);
    
    kruskal(); //板子
    
    cout<<ans<<"\n";
    
	return 0;
}

---

Finished…