Rssqzqyp 2017.7.4

算法最小生成树，算是模版题,不加优化58毫秒
加优化25s左右

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000100;
int n,m;
int fa[maxn];
struct note
{
    int s,v,w;
}e[maxn];
bool cmp(note a,note b)
{
    return a.w<b.w;
}
int ff(int x)
{
    return fa[x]=(fa[x]==x)?x:ff(fa[x]);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    cin>>e[i].s>>e[i].v>>e[i].w;
    sort(e+1,e+m+1,cmp);
    int rest=n-1;
    int ans1=0,ans2=0;
    for(int i=1;i<=m;i++)
    fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        if(!rest) break; 
        int p1,p2;
        p1=ff(e[i].s);
        p2=ff(e[i].v);
        if(p1==p2) continue;
        fa[p1]=p2;
        ans1++;
        rest--;
        ans2=e[i].w;
    }
cout<<ans1<<" "<<ans2;
return 0;
}

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stdio.h>
#include<string.h>
#define Max 1000100
using namespace std;
int fa[Max];
int find(int x)
{
if(fa[x]==x)
return x;
return fa[x]=find(fa[x]);
}
struct road
{
int u,v,c;
}f[Max];
bool cmp(road a,road b)
{
return a.c<b.c;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&f[i].u,&f[i].v,&f[i].c);
}
sort(f+1,f+1+m,cmp);
for(int i=1;i<=m;i++)
{
fa[i]=i;
}
int ans1,ans2;
ans1=0,ans2=0;
int rest;
rest=n-1;
for(int i=1;i<=m;i++)
{
if(!rest)
break;
int x,y;
x=find(f[i].u);
y=find(f[i].v);
if(x==y)
continue;
fa[x]=y;
ans1++;
rest--;
ans2=f[i].c;
}
cout<<ans1<<" "<<ans2<<endl;
return 0;
}

最小生成树裸题

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000010;
struct Edge
{
    int u,v,c;
}e[maxn];
int n,gary,m,p[maxn],ans;
inline int read()
{
    int f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
bool cmp(Edge a,Edge b)
{
    return a.c<b.c;
}
void init()
{   
    n=read();m=read();gary=n-1;
    for(int i=1;i<=m;i++)
    {
        e[i].u=read();
        e[i].v=read();
        e[i].c=read();
    }
}
int find(int x)
{
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}
void work()
{
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=n;i++)
    p[i]=i;
    for(int i=1;i<=m;i++)
    {
        if(!gary) break;
        int x=find(e[i].u),y=find(e[i].v);
        if(x!=y)
        {
            gary--;
            p[x]=y;
            ans=max(e[i].c,ans);
        }
    }
    cout<<n-1<<" "<<ans<<endl;
}
int main()
{
    init();
    work();
}

Accepted

状态 耗时 内存占用

#1 Accepted 8ms 336.0 KiB
#2 Accepted 2ms 360.0 KiB
#3 Accepted 3ms 384.0 KiB
#4 Accepted 2ms 384.0 KiB
#5 Accepted 2ms 372.0 KiB
#6 Accepted 4ms 256.0 KiB
#7 Accepted 4ms 360.0 KiB
#8 Accepted 6ms 384.0 KiB
#9 Accepted 7ms 480.0 KiB
#10 Accepted 7ms 512.0 KiB
---------------------------------------------------
着毫秒数乱七八糟的，强迫症犯了

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<iostream>
#define ll long long
using namespace std;

struct node
{
int l;
int r;
int val;
}a[10005];

int f[10005];
int n , m ,ans,maxn;

int cmp(node x,node y)
{
return x.val < y.val;
}

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

int Kruskal()
{
for(int i = 1;i <= m;i++)
{
int u = a[i].l;
int v = a[i].r;
int uu = find(u);
int vv = find(v);
if(uu == vv)
{
continue;
}else
{
f[vv] = uu;/*f[uu] = vv;*/
ans++;
maxn = max(maxn,a[i].val);
}
}
}

int main()
{
cin >> n >> m;
for(int i = 1;i <= m;i++)
{
cin >> a[i].l >> a[i].r >> a[i].val;
}
for(int i = 1;i <= n;i++)
{
f[i] = i;
}
sort(a+1,a+1+m,cmp);
Kruskal();
cout << ans << " " << maxn <<endl;
return 0 ;
}

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e4 + 7;
const int M = 1e3 + 7;
int n, m, cnt, ans, f[M];

template <class T>
inline void read(T &x){
x = 0;
static char buf = getchar();
for ( ;!isdigit(buf); buf = getchar());
for ( ;isdigit(buf); buf = getchar())
x = x * 10 + buf - 48;
}

struct edge{
int u, v, w;
}way[N];

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

inline void init(){
for (int i = 1; i <= n; i ++)
f[i] = i;
}

int find(int x){
return x == f[x] ? x : f[x] = find(f[x]);
}

void kruskal(){
init();
sort(way + 1, way + m + 1, cmp);
for (int i = 1; i <= m; i ++){
int fu = find(way[i].u), fv = find(way[i].v);
if (fu != fv) cnt ++, f[fv] = fu;
if (cnt == n - 1) {
ans = way[i].w; break ;
}
}
}

void work(){
read(n), read(m);
for (int i = 1; i <= m; i ++)
read(way[i].u), read(way[i].v), read(way[i].w);
kruskal();
cout << cnt << ' ' << ans << endl;
}

int main(){
work(); return 0;
}

没有人发prim的话我来补一个。。给学最小生成树的oier提供个模板。

#include<iostream>
#include<cstdio>
using namespace std;
int dis[305][305],mina[305],u[305],n,m,i,x,y,be,j,k,ans,minx,minn,tot;
int main()
{
    cin>>n>>m;
    minn=0x7fffffff/3;
    for(i=0;i<=n;i++)
    {
        mina[i]=0x7fffffff/3;
        for(j=0;j<=n;j++)
        {
            dis[i][j]=0x7fffffff/3;
        }
    }
    for(i=1;i<=m;i++)
    {
        cin>>x>>y;
        cin>>dis[y][x];
        dis[x][y]=dis[y][x];
        if(dis[x][y]<minn)
        {
            minn=dis[x][y];
            be=x;
        }
    }
    mina[x]=0;
    for(int l=1;l<=n;l++)
    {
        k=0;
    for(i=1;i<=n;i++)
    {
        if(mina[k]>mina[i] && !u[i])
        {
            k=i;
        }
    }
        u[k]=1;
        for(j=1;j<=n;j++)
        {
            if(!u[j] && mina[j]>dis[j][k])
            {
                mina[j]=dis[j][k];
            }
        }
    }
      for(int q=1;q<=n;q++)
        ans=max(mina[q],ans); 
        cout<<n-1<<" "<<ans;
    return 0;
}

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

struct edge_1
{
    int x,y,d;
};

int n,m,cnt,max_d;
vector<int> fa;
vector<edge_1> e;

bool cmp_edge_1(edge_1 x,edge_1 y)
{
    return x.d<y.d;
}

int find_fa_1(int x)
{
    return ((fa[x]==x)?x:(fa[x]=find_fa_1(fa[x])));
}

int unite_1(int x,int y)
{
    if (fa[(fa[y]=find_fa_1(fa[y]))]!=(fa[x]=find_fa_1(fa[x])))
    {
        fa[fa[y]]=fa[x];
        return 1;
    }
    else
        return 0;
}

int main()
{
    while (~scanf("%d%d",&n,&m))
    {
        fa.resize(n+1);
        for (int i=1;i<=n;i++)
            fa[i]=i;
        e.resize(m+1);
        for (int i=1;i<=m;i++)
        {
            int x,y,d;
            scanf("%d%d%d",&x,&y,&d);
            e[i].x=x,e[i].y=y,e[i].d=d;
        }
        sort(e.begin()+1,e.end(),cmp_edge_1);
        cnt=max_d=0;
        for (int i=1;i<=m&&cnt<n-1;i++)
        {
            int suc=unite_1(e[i].x,e[i].y);
            cnt+=suc;
            max_d=max(max_d,e[i].d*suc);
        }
        printf("%d %d\n",cnt,max_d);
    }
}

#include <bits/stdc++.h>
using namespace std;
int f[305];
struct edge
{
    int from,to,len;
}road[10005];
bool comp(edge a,edge b){
    return a.len<b.len;
}
int getf(int x)
{
    return f[x]==x?x:f[x]=getf(f[x]);
}
int main()
{
    int n,m,maxw=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&road[i].from,&road[i].to,&road[i].len);
    std::sort(road+1,road+m+1,comp);
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1,j=0;i<=m && j<n-1;i++) {
        int p1=getf(road[i].from);
        int p2=getf(road[i].to);
        if(p1!=p2) {
            maxw=road[i].len;
            f[p1]=p2;
        }
    }
    printf("%d %d",n-1,maxw);
    return 0;
}

记录信息
评测状态 Accepted
题目 P1190 繁忙的都市
递交时间 2016-03-20 11:49:59
代码语言 C++
评测机 VijosEx
消耗时间 0 ms
消耗内存 368 KiB
评测时间 2016-03-20 11:50:01
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 368 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 364 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 368 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 368 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 368 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 364 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 368 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 368 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 368 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 368 KiB, score = 10
Accepted, time = 0 ms, mem = 368 KiB, score = 100
代码
#include<cstdio>
#include<algorithm>
using namespace std;

const int MaxN = 300 + 10, MaxM = 10000 + 10;

int N, M, A, B, Max;

struct Node {
bool root;
int parent;
}node[MaxN];

struct Eage {
int To, From, Cost;
bool operator < (const Eage& Element) const {
return Element.Cost > Cost;
}
}E[MaxM];

int getInt() {
int Return = 0;
char Get = getchar();
while(Get >= '0' && Get <= '9') {
Return = Return * 10 + (Get - '0');
Get = getchar();
}
return Return;
}

int Find(int Element) {
int theRoot = Element;
while (!node[theRoot].root)theRoot = node[theRoot].parent;
int parentNode;
int Now = Element;
while (Now != theRoot) {
parentNode = node[Now].parent; node[Now].parent = theRoot; Now = parentNode;
}
return theRoot;
}

void Unite(int rootA, int rootB)
{
if (node[rootA].parent < node[rootB].parent) {
node[rootB].parent += node[rootA].parent;
node[rootA].root = 0;
node[rootA].parent = rootB;
}
else {
node[rootA].parent += node[rootB].parent;
node[rootB].root = 0;
node[rootB].parent = rootA;
}
}

int main() {
N = getInt(); M = getInt();
for(int i = 1; i <= N; ++i) {
node[i].root = 1;
node[i].parent = i;
}
for(int i = 1; i <= M; ++i) {
E[i].From = getInt();
E[i].To = getInt();;
E[i].Cost = getInt();
}
sort(E + 1, E + M + 1);
for(int i = 1, j = N; j > 1; ++i) {
A = Find(E[i].From); B = Find(E[i].To);
if(A != B) {
Unite(A, B);
Max = max(Max, E[i].Cost); --j;
}
}
printf("%d %d", N - 1, Max);
return 0;
}

此题似乎并不需要生成树，二分答案即可。
时间复杂度为O(nlogn)

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define NMAX 300

struct Edge {
    Edge() : u(0), v(0), w(0) {}
    Edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {}

    int u;
    int v;
    int w;
};  // struct Edge

typedef vector<Edge *>::iterator iterator_t;

static int n;
static int m;
static int size;
static int set[NMAX + 10];
static vector<Edge *> edges;
static int answer;

bool compare(const Edge *a, const Edge *b) {
    return a->w < b->w;
}

inline void make_set() {
    size = n;

    for (int i = 1; i <= n; i++) {
        set[i] = i;
    }  // for
}

inline int find_set(int x) {
    return x == set[x] ? x : set[x] = find_set(set[x]);
}

inline void union_set(int x, int y) {
    x = find_set(x);
    y = find_set(y);

    if (x != y) {
        set[x] = y;
        size--;
    }
}

void initialize() {
    scanf("%d %d", &n, &m);

    edges.reserve(m);
    int x, y, c;
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &x, &y, &c);

        if (x == y)
            continue;

        Edge *p = new Edge(x, y, c);
        edges.push_back(p);
    }  // for

    sort(edges.begin(), edges.end(), compare);
}

void quit() {
    printf("%d %d", n - 1, answer);
}

bool test(int limit) {
    make_set();

    for (iterator_t beg = edges.begin();
         beg != edges.end() and (*beg)->w <= limit;
         beg++) {
        Edge *e = *beg;
        union_set(e->u, e->v);
    }  // for

    return size == 1;
}

int main() {
    initialize();

    int left = 0, right = edges.size() - 1;
    while (right - left > 1) {
        int mid = (left + right) >> 1;

        bool flag = test(edges[mid]->w);
        if (flag) {
            right = mid;
        } else {
            left = mid;
        }
    }  // while

    if (left != right and !test(edges[left]->w)) {
        left = right;
    }

    answer = edges[left]->w;

    quit();
    return 0;
}  // function main

大神们，这一道题能用prim做么？在线等

半裸的Krustal
#include <cstdio>
#include <cstring>
#include <algorithm>

const int maxn=305;
const int maxm=maxn*maxn/2;
int p[maxn];

struct edge
{
int from,to;
int weight;
}road[maxm];

bool operator < (const edge& A,const edge& B)
{
return A.weight < B.weight;
}
int getP(int x)
{
return p[x]==x?x:p[x]=getP(p[x]);
}
int main()
{
int N,M;
scanf("%d%d",&N,&M);
for(int i=0;i<M;i++) {
scanf("%d%d%d",&road[i].from,&road[i].to,&road[i].weight);
}
std::sort(road,road+M);

int maxW=0;
for(int i=1;i<=N;i++) p[i]=i;
for(int i=0,j=N;j>1;i++) {
int p1=getP(road[i].from);
int p2=getP(road[i].to);
if(p1!=p2) {
maxW=road[i].weight;
p[p1]=p2;
j--;
}
}

printf("%d %d",N-1,maxW);
return 0;
}

该题显然用n-1条边将每个节点连接。
要求最大权值最小，说明构造的最小生成树最大的边权输出即可。
因为 最小生成树以贪心的方法构造，其中选的边都是可用的中最小的，假如换掉其中一条边，必然使总权值变大，且最大边权要么仍等于最小生成树的最大边权，要么比其大。 因为 若换的为最小生成树中不是最大边权的边，那么最大边权保持不变，否则使得最大边权变大。
由此可以得出最大边权最小必然是最小生成树的最大边权。

由此得出算法 Kruscal算法即可。

###代码如下

program p1190;
type rec=record
s,e,v:longint;
end;
var n,m:longint;
ans,i,j,k:longint;
father:array[1..300] of integer;
map:array[1..90000] of rec;

function max(a,b:longint):longint;
begin
if a>b then exit(a);
exit(b);
end;

procedure qsort(i,j:longint);
var l,r,mid:longint;
temp:rec;
begin
l:=i;
r:=j;
mid:=map[(l+r)>>1].v;
while l<=r do
begin
while map[l].v<mid do inc(l);
while map[r].v>mid do dec(r);
if l<=r
then
begin
temp:=map[l];
map[l]:=map[r];
map[r]:=temp;
inc(l);
dec(r);
end;
end;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;

function find(x:longint):longint;
begin
if father[x]=x then exit(x);
father[x]:=find(father[x]);
exit(father[x]);
end;

procedure unite(a,b:longint);
begin
father[find(father[a])]:=find(father[b]);
end;
begin
readln(n,m);
for i:=1 to m do
begin
readln(map[i].s,map[i].e,map[i].v);
map[i+m].s:=map[i].e;
map[i+m].e:=map[i].s;
map[i+m].v:=map[i].v;
end;
qsort(1,2*m);
for i:=1 to n do father[i]:=i;
for i:=1 to 2*m do
begin
if find(map[i].s)<>find(map[i].e)
then
begin
unite(map[i].s,map[i].e);
ans:=max(ans,map[i].v);
end;
end;
write(n-1,' ',ans);
end.
###评测结果

测试数据 #0: Accepted, time = 23 ms, mem = 1840 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1840 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1840 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1840 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 1844 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1840 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 1840 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 1844 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1840 KiB, score = 10
测试数据 #9: Accepted, time = 46 ms, mem = 1840 KiB, score = 10
Accepted, time = 99 ms, mem = 1844 KiB, score = 100

#include<cstdio>
#include<algorithm>

using namespace std;

struct kruskal{
int a,b,value;
};

int n,m,son[1001],father[1001],total=0;
kruskal edge[10000];

bool cmp(const kruskal & a,const kruskal & b){
return a.value<b.value;
}

int find(int x){
return x==father[x] ? x : find(father[x]);
}

bool join(int x,int y){
x=find(x);
y=find(y);
if(x==y){
return false;
}
else if(son[x]<=son[y]){
father[x]=y;
son[y]+=son[x];
}
else{
father[y]=x;
son[x]+=son[y];
}
return true;
}

int main(){
scanf("%d%d",&n,&m);
for(int j=0;j<k;j++){
sum=0;
total=0;
for(int i=1;i<=n;i++){
father[i]=i;
son[i]=1;
}

for(int i=0;i<m;i++){
scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].value);
}

sort(edge,edge+m,cmp);

for(int i=0;i<m;i++){
if(join(edge[i].a,edge[i].b)){
total++;
sum+=edge[i].value;
}
if(total==n-1){
printf("%d %d",total edge[i].value);
return 0;
}
}
}

优先队列优化的Kruskal+并查集
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<algorithm>
using namespace std;
struct Edge
{
int u, v, dis;
bool operator< (const Edge &rhs) const
{
return dis > rhs.dis;
}
};
int n, m, maxs = 0;
priority_queue<Edge> e;
int fa[311];
int FIND(int x)
{
if(fa[x] == x)return x;
else return fa[x] = FIND(fa[x]);
}
int main()
{
//freopen("test.in","r",stdin);
//freopen("test.out","w",stdout);
ios::sync_with_stdio(false);
cin >> n >> m;
int tu, tv, tdis;
for(int i = 0; i < m; ++i)
{
cin >> tu >> tv >> tdis;
e.push((Edge){tu, tv, tdis});
}
memset(fa, 0, sizeof(fa));
for(int i = 1; i <= n; ++i)fa[i] = i;
while(!e.empty())
{
Edge cur = e.top();
e.pop();
int a = FIND(cur.u), b = FIND(cur.v);
if(a == b)continue;
fa[a] = b;
maxs = cur.dis;
}
cout << n - 1 << " " << maxs << endl;
return 0;
}

program p1190;
var
sum,max,i,j,min,x,y,z,n,m,k:longint;
a:array[1..1000,1..1000]of longint;
b,c,d:array[1..1000]of longint;
procedure prim;
begin
sum:=0;
for i:=1 to n do begin d[i]:=a[1,i];b[i]:=1;end;
for j:=2 to n do begin
min:=maxlongint;
for i:=1 to n do
if (d[i]<>0)and(d[i]<min) then begin min:=d[i];k:=i;end;
sum:=sum+1;if d[k]>max then max:=d[k];d[k]:=0;
for i:=1 to n do
if (a[k,i]<d[i])and(i<>k) then begin d[i]:=a[k,i];b[i]:=k;end;
end;
end;
begin
readln(n,m);
for i:=1 to n do for j:=1 to n do a[i,j]:=1000000000;
for i:=1 to n do a[i,i]:=0;
for i:=1 to m do begin
readln(x,y,z);a[x,y]:=z;a[y,x]:=z;end;
prim;
writeln(sum,' ',max);
end.
秒杀，爽

#include<algorithm>
#include<iostream>
using namespace std;
struct q
{
int a,b,c;
}p[100001];
int f[100001];
int c(q a,q b)
{
return a.c<b.c;
}
int find(int x)
{
if(f[x]!=x)
f[x]=find(f[x]);
return f[x];
}
main()
{
int m,n,i,x,y,k=0;
long long s=0,t=0;
cin>>n>>m;
cout<<n-1<<' ';
for(i=1;i<=n;i++)
f[i]=i;
for(i=1;i<=m;i++)
cin>>p[i].a>>p[i].b>>p[i].c;
sort(p+1,p+m+1,c);
for(i=1;i<=m;i++)
{
x=find(p[i].a);
y=find(p[i].b);
if(x!=y)
{
f[x]=y;
s+=p[i].c;
k++;
if(k==n-1)
{
cout<<p[i].c;
return 0;
}
}
}
}

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 300;

struct EDGE {
int a;
int b;
int c;
} w[10000];

int n, m;
int p[MAXN + 1];

bool cmp(const EDGE e1, const EDGE e2)
{
return (e1.c < e2.c);
}

int find(int a)
{
int x = p[a];
while (p[x] != x) x = p[x];
return x;
}

void union_set(int a, int b)
{
a = find(a);
b = find(b);
p[b] = a;
}

int Kruskal(int & s, int & l)
{
int i;
for (i = 1; i <= n; ++i) p[i] = i;

s = l = 0;
for (i = 1; i <= m; ++i) {
if (find(w[i].a) != find(w[i].b)) {
union_set(w[i].a, w[i].b);
++s;
if (w[i].c > l) l = w[i].c;
}
}
return 0;
}

int main()
{
cin >> n >> m;

int i;
for (i = 1; i <= m; ++i) cin >> w[i].a >> w[i].b >> w[i].c;

sort(&w[1], &w[m + 1], cmp);

int s, l;
Kruskal(s, l);

cout << s << " " << l;

return 0;
}