Untitled

 avatar
user_0483151
plain_text
22 days ago
1.6 kB
2
Indexable
// y.ha
#include <bits/stdc++.h>
#define cook '\n'
#define maxn 10001
#define Task "C"
using namespace std;
struct D {
    int a,b,c ;
} ;
int n,m,p[1001],res1 = 0;
D in[maxn] ;
vector<int> best ;
bool ss(D x,D y) {
    if ( x.c != y.c ) return x.c < y.c ;
    return x.a < y.a ;
}

void inp() {
    cin >> n >> m ;
    for ( int i = 1; i <= m; i++ ) {
        cin >> in[i].a >> in[i].b >> in[i].c  ;
        if ( in[i].a > in[i].b ) swap(in[i].a,in[i].b) ;
    }
    sort(in + 1,in + 1 + m, ss) ;
}

int Find(int u) {
    if ( !p[u] ) return u ;
    int x = Find(p[u]) ;
    p[u] = x ;
    return x ;
}

void Solve(int u,int v,int val) {
    int x = Find(u), y = Find(v) ;
    if ( x == y ) return ;
    res1 += val ;
    p[y] = x ;
}

int main()
{
    ios_base::sync_with_stdio(0) ;
    cin.tie(nullptr) ;
    if(fopen(Task".INP","r")) {
        freopen(Task".INP","r",stdin);
        freopen(Task".OUT","w",stdout);
    }
    inp() ;
    for ( int i = 1; i <= m; i++ ) {
        int a = in[i].a, b = in[i].b, c = in[i].c ;
        int x = res1 ;
        Solve(a,b,c) ;
        if ( res1 > x ) best.push_back(i) ;
    }
    int ans = res1,ans2 = 100000000 ;
    for ( int i : best ) {
        memset(p,0,sizeof(p)) ;
        res1 = 0 ;
        for ( int j = 1; j <= m; j++ ) {
            if ( j == i ) continue ;
            int a = in[j].a, b = in[j].b, c = in[j].c ;
            Solve(a,b,c) ;
        }
        if ( res1 < ans2 ) ans2 = res1;
    }
    cout << ans << " " << ans2  ;
    return(0) ;
}
Leave a Comment