[C++知识库]P2330 繁忙的都市（生成树）C++

P2330 [SCOI2005]繁忙的都市

输入：

4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8

输出：

3 6

//prim
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstdlib>
#include <algorithm>
#include<string.h>
#include<math.h>
#define llu unsigned long long
using namespace std;
int g[310][310];
int n,m,a,b,c,minn[310],mmax=-1;
bool u[310];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=c;
        g[b][a]=c;
    }
    memset(minn,0x7f,sizeof(minn));    
    minn[1]=0;
    memset(u,1,sizeof(u));
    for(int i=1;i<=n;++i){
        int k=0;
        for(int j=1;j<=n;j++)
            if(u[j]&&(minn[j]<minn[k]))
                k=j;
        u[k]=0;
        for(int j=1;j<=n;j++)
            if(u[j] && g[k][j]!=0 && g[k][j]<minn[j])
                minn[j]=g[k][j];
    }
    for(int i=1;i<=n;++i){
        if(minn[i]>mmax)
            mmax=minn[i];
    }
    printf("%d %d",n-1,mmax);
    return 0;
}

//克鲁斯卡尔
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstdlib>
#include <algorithm>
#include<string.h>
#include<math.h>
#include <algorithm>
using namespace std;
int m, n, u, v, c, maxn, k;
int fa[301];
int find(int x) {
    if(fa[x]!=x) 
        fa[x]=find(fa[x]);
    return fa[x];
}
void unionn(int x,int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx != fy) fa[fx]=fy;
}
struct Node {
    int x, y, v;
    bool operator < (const Node &b) const {
        return v<b.v;
    }
}a[51000];
int main() {
    cin >> n >> m;
    for (int i=1; i<=m; i++) {
        cin >> u >> v >> c;
        a[i]=(Node){u, v, c};
    }
    for (int i=1; i<=n; i++) fa[i]=i;
    sort(a+1,a+m+1);
    for (int i=1; i<=m; i++) {
        if (find(fa[a[i].x]) != find(fa[a[i].y])) {
            unionn(a[i].x, a[i].y);
            maxn = a[i].v;
            k++;
        }
        if (k == n-1) break;
    }
    cout<< n-1 << " " <<maxn; 
    return 0;
}