13 条题解

  • 6
    @ 2021-9-14 20:38:38

    使用 Kruskal 算法解决。

    主要思路：把边以边权从小到大排序。接下来从头开始枚举边。如果边会使得后面的图一定不是树（即出现环），则跳过。如果总共已经 n−1n-1 条边，则结束。如果所有枚举完后不到 n−1n-1 条边，则返回不行（此题没有）。

    那么如何判断是否有环？最好的方法就是使用优化的并查集。

    代码：

    #include<bits/stdc++.h>
using namespace std;
#define int long long
int m,n,cnt,sum;
int fa[100009];
struct edge{
    int w;
    int u,v;
};
edge e[200009];
bool cmp(edge x,edge y){
    return x.w<y.w;
}
void init(){
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
    for(int i=1;i<=n;i++) fa[i]=i;
}
int anc(int k){
    if(fa[k]==k) return k;
    else return fa[k]=anc(fa[k]);
}
void relate(int x,int y){
    if(x<y) swap(x,y);
    fa[anc(y)]=anc(x);
}
signed main(){
    init();
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=m;i++){
        if(anc(e[i].u)!=anc(e[i].v)){
            cnt++;
            relate(e[i].u,e[i].v);
            sum+=e[i].w;
        }
        if(cnt==n-1) break;
    }
    if(cnt!=n-1) cout<<"No solution";
    else cout<<sum;
    return 0;
}
    • 3
      @ 2022-7-19 17:57:50

      这里讲解一下 KruskalKruskal算法。

      KruskalKruskal的主要思想：贪心。

      既然我要求的是最小权值，那么我对所有边进行排序，然后一条一条看就行了。

      那么怎么样的边是可选的呢？

      很显然，如果一边上两个点（未连接时）在两个连通分量中，那么这条边是可选的（毕竟不连白不连）；而如果这两点在一个连通分量中，那么这条边就不可选了。

      最后，因为树的权值最小，当边数为 n−1n-1时，程序结束。

      注意权值数据范围。

      代码如下：

      #include<bits/stdc++.h>
#define maxn 200005
using namespace std;
int n,m,s,cnt=1,fa[maxn];
struct Edge{
    int u,v,w;
} e[maxn];
int find(int k){
    if(fa[k]==k)return k;
    return fa[k]=find(fa[k]);
}
bool cmp(Edge a,Edge b){
    return a.w<b.w;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)
        cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=m&&cnt<n;i++){
        int u=e[i].u,v=e[i].v;
        if(find(u)==find(v))continue;
        s+=e[i].w;
        cnt++;
        fa[find(u)]=find(v);
    }if(cnt<n)cout<<-1;
    else cout<<s;
    return 0;
}
      • 2
        @ 2022-11-11 19:39:56

        怎么都不约而同地使用 Kruskal 去了，堆优化的 Prim 也可以通过这一题的。

        Prim 算法是什么 & 算法原理

        Prim 算法与最短路中的 Dijsktra 算法有点相像。我们随便选取一个根，接下来从根节点向外贪心地选取最小的边，将其加入至最小生成树中即可，其中，选取最小的边的操作可以用堆优化至 O(log⁡n)O(\log n)。

        总的复杂度：O(nlog⁡n)O(n\log n)。

        #include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)

const int MAXN = 1e5 + 5;
struct _node {
    int v, w;
    bool operator < (const _node b) const {
        return w > b.w;
    }
};
vector<_node> G[MAXN];
int n, m, dis[MAXN];
bool vis[MAXN];

int prim() {
    int cnt = 0, ret = 0;
    memset(dis, 0x3f, sizeof dis);
    priority_queue<_node> pq;
    pq.push({1, 0});
    while (pq.size() && cnt < n) {
        auto [u, w] = pq.top(); pq.pop();
        if (vis[u]) continue;
        cnt++; ret += w;
        vis[u] = true;
        for (auto [v, x]:G[u]) {
            if (x < dis[v]) {
                dis[v] = x;
                pq.push({v, dis[v]});
            }
        }
    }
    return ret;
}

signed main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    cout << prim() << endl;
    return 0;
}
        • 2
          @ 2022-2-19 13:30:24

          使用 Kruskal 解决。

          Kruskal 使用的是一个贪心算法，首先把边权按从小到大排序，然后依次加边，如果加出了环，那就不加了。如果有 n−1n-1 条边那么就已经得出答案。

          证明：如果有一条边 uu 删除后可以用其他边 vv 顶替，根据排序方法可知 u≤vu\le v，也就是说，换上 vv 之后不能使答案变优。

          注意最终答案最大可以在 101110^11 的级别，需要开 long long。

          代码瓶颈在排序，时间复杂度 O(mlog⁡m)O(m\log m)。

          #include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+5;
int father[maxn],m,n,u,v,w,ans;
struct edge{
	int x,y,z;
	bool operator <(const edge &a) const{
		return z<a.z;
	}
};
vector<edge> G;
void makeSet(int n){
	for(int i=1;i<=n;i++)
		father[i]=i;
}
int findSet(int x){
	if(father[x]==x)
		return x;
	return father[x]=findSet(father[x]);
}
void Kruskal(){
	makeSet(n);
	sort(G.begin(),G.end());
	int edgeNum=0;
	for(int i=0;i<m;i++){
		int x=findSet(G[i].x),y=findSet(G[i].y);
		if(x!=y){
			father[x]=y;
			ans+=G[i].z;
			edgeNum++;
		}
		if(edgeNum==n-1)
			return;
	}
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%lld%lld%lld",&u,&v,&w);
		G.push_back(edge({u,v,w}));
	}
    Kruskal();
	printf("%lld\n",ans);
	return 0;
}
          • 1
            @ 2023-11-16 15:53:45

            最小生成树个人喜欢 KruskalKruskal 算法

            前置知识：贪心，并查集

            原理

            最小生成树：一个无向连通图，边权值和最小的生成树

            既然是边权值和最小，那么我们可以用贪心的思想，将边权从小到大排序，依次插入最小生成树中。

            这是具体的排序后插入的操作：

            1. 如果 uu，vv 两点之间没有路径，我们就将这条边加入到最小生成树中；
            2. 如果 uu，vv 两点之间已经在最小生成树中有路径，或者形成了一个环，那么我们就把这条边"扔掉"。

            重复以上步骤，我们可以顺便统计最小生成树的边权和，直到最小生成树中有 n−1n-1 条边(也就是构成了一棵树)。

            至于实现有无路径，我们可以使用并查集实现。

            这样子的时间复杂度最优是 O(mlog⁡m)O(m \log{m})

            注意!!! 开long long!!!，0≤wi≤1060 \le w_i \le 10^6!!!

            这里提一嘴另一种求解最小生成树的方式:Prim，题解(link)可以参考楼下的 xiaoququ 大佬。

            它与 KruskalKruskal 的区别就在于一个是加点(Prim)，一个是加边(Kruskal)，而且 Prim 类似于最短路中的 Dijsktra 算法。

            AC code

            // Kruskal
const int N = 2e5 + 5;
typedef long long ll;

struct Edge{
	ll u, v, w;
}e[N];

bool cmp(Edge x, Edge y){
	return x.w < y.w;
}

int find(int x){
	if (fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}

int main(){

	sort (e + 1, e + m + 1, cmp);
	ll cnt = 0;
	int tot = 0;
	for (int i = 1; i <= m; ++i){
		int u = e[i].u, v = e[i].v, w = e[i].w;
		int fu = find(u), fv = find(v);
		
		if (fv == fu) continue;
		fa[fu] = fv;
		tot++;
		cnt += w;
		if (tot == n - 1) break;
	}
	return 0;
}
            • 0
              @ 2023-9-15 21:12:34

              本题目可以用 最小生成树之 Kruskal 算法 解

              #include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
const int M = 2e5 + 10;
int fa[N], n, m;
long long ret; // 不开 long long 见祖宗
struct node {
	int x, y, z;
}e[M];

bool cmp(node n1, node n2) {
	return n1.z < n2.z;
}
void INIT() { // 初始化每个节点的父节点都是自己
	for (int i = 1; i <= n; i++) {
		fa[i] = i; // 相当于一个图有 n 个节点，也有 n 个联通块
	} // 可以说是一个图没有边，初始化，Kruskal 的基本思想就是贪心
} 
int dfs(int x) { // 并查集，不懂看后面
	return fa[x] == x ? x : fa[x] = dfs(fa[x]);
    // fa[x] = dfs(fa[x]) 是一个路径压缩
}
void kruskal() {
	int cnt = 0;
	sort(e+1, e+m+1, cmp); // 排序所有的边
	for (int i = 1; i <= m; i++) { // 枚举所有的边
		int fx = dfs(e[i].x); // find
		int fy = dfs(e[i].y);
		if (fx != fy) { // 可以通过并查集函数来理解
			fa[fx] = fy; //
			ret += e[i].z;
			cnt++; // 这个没有用，但是这个可以计数是否可以构成最小生成树
		}
	}
	cout << ret;
}

int main() {
    cin >> n >> m;
	INIT();
    for (int i = 1; i <= m; i++) {
    	scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].z);
	}
	kruskal();
    return 0;
}

              并查集

              • 0
                @ 2023-8-10 12:54:55 
                #include<bits/stdc++.h>
using namespace std;
#define int long long
int m,n,cnt,sum;
int fa[100009];
struct edge{
    int w;
    int u,v;
};
edge e[200009];
bool cmp(edge x,edge y){
    return x.w<y.w;
}
void init(){
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
    for(int i=1;i<=n;i++) fa[i]=i;
}
int anc(int k){
    if(fa[k]==k) return k;
    else return fa[k]=anc(fa[k]);
}
void relate(int x,int y){
    if(x<y) swap(x,y);
    fa[anc(y)]=anc(x);
}
signed main(){
    init();
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=m;i++){
        if(anc(e[i].u)!=anc(e[i].v)){
            cnt++;
            relate(e[i].u,e[i].v);
            sum+=e[i].w;
        }
        if(cnt==n-1) break;
    }
    if(cnt!=n-1) cout<<"No solution";
    else cout<<sum;
    return 0;
}
                • 0
                  @ 2023-3-25 9:36:19 
                  #include<bits/stdc++.h>
using namespace std;
#define int long long
int m,n,cnt,sum;
int fa[100009];
struct edge{
int w;
int u,v;
};
edge e[200009];
bool cmp(edge x,edge y){
return x.w<y.w;
}
void init(){
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
for(int i=1;i<=n;i++) fa[i]=i;
}
int anc(int k){
if(fa[k]==k) return k;
else return fa[k]=anc(fa[k]);
}
void relate(int x,int y){
if(x<y) swap(x,y);
fa[anc(y)]=anc(x);
}
signed main(){
init();
sort(e+1,e+m+1,cmp);
for(int i=1;i<=m;i++){
if(anc(e[i].u)!=anc(e[i].v)){
cnt++;
relate(e[i].u,e[i].v);
sum+=e[i].w;
}
if(cnt==n-1) break;
}
if(cnt!=n-1) cout<<"No solution";
else cout<<sum;
return 0;
}
                  • 0
                    @ 2022-8-18 17:05:49

                    KruskalKruskal 解决问题，ansans 注意开 longlonglong long ,不然会爆

                    下面是 ACAC 代码：

                    #include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    bool flag=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
            flag=0;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return (flag?x:~(x-1));
}
int n,m,k;
long long ans=0;
int f[100001];
struct edge
{
	int x,y,z;
}a[200001];
inline void init()
{
	for(int i=1;i<=n;i++)
	{
		f[i]=i;
	}
}
inline int find(int x)
{
	return x==f[x]?x:f[x]=find(f[x]);
}
inline bool cmp(edge a,edge b)
{
    return a.z<b.z;
}
int main()
{
	n=read();m=read();
	init();
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		a[i].x=read();a[i].y=read();a[i].z=read();
	}
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		int fx=find(a[i].x),fy=find(a[i].y);
		if(fx==fy)
		{
			continue;
		}
		f[fx]=fy;
		ans+=a[i].z;	
	}
	cout<<ans;
	return 0;
}

                    完结撒花！

                    • -1
                      @ 2023-3-23 20:11:34 
                      #include<bits/stdc++.h>
using namespace std;
#define int long long
int m,n,cnt,sum;
int fa[100009];
struct edge{
    int w;
    int u,v;
};
edge e[200009];
bool cmp(edge x,edge y){
    return x.w<y.w;
}
void init(){
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
    for(int i=1;i<=n;i++) fa[i]=i;
}
int anc(int k){
    if(fa[k]==k) return k;
    else return fa[k]=anc(fa[k]);
}
void relate(int x,int y){
    if(x<y) swap(x,y);
    fa[anc(y)]=anc(x);
}
signed main(){
    init();
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=m;i++){
        if(anc(e[i].u)!=anc(e[i].v)){
            cnt++;
            relate(e[i].u,e[i].v);
            sum+=e[i].w;
        }
        if(cnt==n-1) break;
    }
    if(cnt!=n-1) cout<<"No solution";
    else cout<<sum;
    return 0;
}
                      • -1
                        @ 2022-3-16 16:25:22

                        使用 Kruskal 算法。

                        有环的情况可以用并查集跳过。

                        #include<bits/stdc++.h>
using namespace std;
long long n,m,fa[100005],cnt,ans,s[100005];
struct node{
	long long u,v,w;
}a[200005];
bool cmp(node x,node y){
	return x.w<y.w;
}
int find(int x){
	if(fa[x]==x)
		return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y){
	if(s[x]<s[y])
		swap(x,y);
	int fx=find(x),fy=find(y);
	fa[fy]=fx,s[fx]+=s[fy];
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%lld%lld%lld",&a[i].u,&a[i].v,&a[i].w);
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=n;i++)
		fa[i]=i;
	for(int i=1;i<=m;i++){
		if(find(a[i].u)==find(a[i].v))
			continue;
		merge(a[i].u,a[i].v);
		cnt++;
		ans+=a[i].w;
		if(cnt==n-1)
			break;
	}
	printf("%lld",ans);
	return 0;
}
                        • -3
                          @ 2023-8-10 12:55:33

                          #include<bits/stdc++.h> using namespace std; #define int long long int m,n,cnt,sum; int fa[100009]; struct edge{ int w; int u,v; }; edge e[200009]; bool cmp(edge x,edge y){ return x.w<y.w; } void init(){ cin>>n>>m; for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w; for(int i=1;i<=n;i++) fa[i]=i; } int anc(int k){ if(fa[k]k) return k; else return fa[k]=anc(fa[k]); } void relate(int x,int y){ if(x<y) swap(x,y); fa[anc(y)]=anc(x); } signed main(){ init(); sort(e+1,e+m+1,cmp); for(int i=1;i<=m;i++){ if(anc(e[i].u)!=anc(e[i].v)){ cnt++; relate(e[i].u,e[i].v); sum+=e[i].w; } if(cntn-1) break; } if(cnt!=n-1) cout<<"No solution"; else cout<<sum; return 0; }

                          • -4
                            @ 2021-5-17 22:34:16

                            注意：

                            • 不要把洛谷AC代码移过来，注意数据范围
                            • 不要用int！！

                            不要复制下面的代码

                            #include<bits/stdc++.h>
using namespace std;
int n,m;
struct Edge{
int u,v;
long long len;
}e[2000₁0];

bool cmp(Edge a,Edge b){
return a.len<=b.len;
}
int fa[100010];
void init(){
for(int i=1;i<=n;i++)fa[i]=i;
}
int get(int x){
if(fa[x]==x)return x;
return fa[x]=get(fa[x]);
}
void merge(int x,int y){
x=get(x);
y=get(y);
if(x!=y){
fa[x]=y;
}
}
int kruskal(int n,int m){
long long sum=0;
init();
sort(e,e+m,cmp);
for(int i=0;i<m;i++){
int fu=get(e[i].u);
int fv=get(e[i].v);
if(fu!=fv){
fa[fv]=fu;
sum+=e[i].len;
}
}
return sum;
}
int mian(){
cin>>n>>m;
for(int i=0;i<m;++i)cin>>e[i].u>>e[i].v>>e[i].len;
cout<<kruskal(n,m)<<endl;
return 0;
}
                            • 1

                            【模板】最小生成树

                            信息

                            ID
                            91
                            时间
                            1000ms
                            内存
                            256MiB
                            难度
                            3
                            标签
                            递交数
                            737
                            已通过
                            230
                            上传者
                            1. 关于
                            2. 联系我们
                            3. 隐私
                            4. 服务条款
                            5. 版权申诉
                            6. Language
                            7. 兼容模式
                            8. 主题
                            2. © 2021-2024 Hydro.ac
                            4. Worker 1 in 148ms
                            5. Hydro v4.11.2 Professional