Untitled
// 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