欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

ural 1160

程序员文章站 2024-01-12 08:03:04
...

最小生成树  第一次敲 套用几个函数 其实挺容易的

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
struct node
{
    int u,v,w;
    void f(int a, int b, int c)
    {
        u = a;
        v = b;
        w = c;
    }
    bool operator < (const node & e) const
    {
        return w < e.w;
    }
};
vector<node>q,qq;
int p[2000],r[2000];

int findd(int x)
{
    return p[x] == x ? x : p[x] = findd(p[x]);
}
int main()
{
    int n,m;
    node cc;
    scanf("%d%d",&n,&m);
    for(int i = 0; i < m; i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        cc.f(a,b,c);
        q.push_back(cc);
    }
    sort(q.begin(), q.end());
    int ans = 0;
    for(int i = 0; i <= n; i++)
        p[i] = i;
    for(int i = 0; i < m; i++)
    {
        int x = findd(q[i].u), y = findd(q[i].v);
        if(x != y)
        {
            ans = q[i].w;
            qq.push_back(q[i]);
            p[x] = y;
        }
    }
    printf("%d\n",ans);
    int len = qq.size();
    printf("%d\n",len);
    for(int i = 0; i < len; i ++)
        printf("%d %d\n",qq[i].u,qq[i].v);
    return 0;
}