UVA908 题解

· · 题解

题目大意

此题有多组数据，且不会告诉你数据组数。（一开始我没看到，WA 了半天）

分两部分处理。

给你一个有 n 个点，n-1 条边的图，求此图的最小生成树。

不管前 n-1 条边，再给你 k,m 条边（是分开输入的），求最小生成树。

前置知识

很明显，是 最小生成树 。

推荐板子题：P3366【模板】最小生成树 。

具体思路

我们先看第一部分：

很明显，n 个点 n-1 条边的连通图，就是一棵树。一颗树的最小生成树就是那 n-1 条边的边权和。

第二部分：就是一个最小生成树板子，这里使用 Kruskal 实现。

实现

坑点：

  1. 在最后一组数据读完后不能有多余换行（我也不知道为什么）。

  2. 多测要清空。

代码：

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

struct edge{
    int u,v,w;
}g[Max];
int fa[Max],n,m,ans;
int a,b,c,cnt,k,cacnt;

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

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

void add(int uu,int vv,int ww){
    g[++cnt].u=uu;
    g[cnt].v=vv;
    g[cnt].w=ww; 
}

void kruskal(){

    sort(g+1,g+m+1,cmp);

    for(int i=1;i<=m;i++){

        int u=find(g[i].u);
        int v=find(g[i].v);

        if(u==v) continue;
        ans+=g[i].w;
        fa[v]=u;
        cnt++;

    }
}
int main(){

    while(cin>>n){
        cnt=0; 
        if(cacnt!=0) puts("");
        cacnt++;

        //第一部分 
        for(int i=1;i<=n-1;i++){
            scanf("%d%d%d",&a,&b,&c);
            ans+=c;
        }
        printf("%d\n",ans); ans=0;

        //第二部分 
        scanf("%d",&k);
        for(int i=1;i<=k;i++){
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
        }
            scanf("%d",&m);
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        }m+=k;
        for(int i=1;i<=m;i++) fa[i]=i;

        kruskal();//板子 
        printf("%d\n",ans);
        ans=0;
    }

}