Go to diff to previous submission
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdint.h> #include <ctype.h> #include <math.h> #include <string> #include <vector> #include <map> #include <set> #include <algorithm> using namespace std; typedef pair <int, int> PII; typedef long long int LL; typedef vector <int> VI; typedef vector <LL> VLL; #define FOR(i, a, b) for ( int i = a; i < b; ++i ) #define FORD(i, a, b) for ( int i = a-1; i >= 0; --i ) #define FILL(x, v, n) for ( int _i = 0; _i < n; ++_i ) x[_i] = v; const int MAX_V = 2001; const int MAX_E = 1000005; struct Edge { int a, b; LL w; }; int uf[ MAX_V ]; Edge edge[ MAX_E ]; struct UnionFind { int N, numSets; void Init ( int n ) { N = n; numSets = N; FOR(i,0,N) uf[ i ] = i; } void Union ( int i, int j ) { if ( !IsSameSet( i, j ) ) { --numSets; int fi = Find( i ), fj = Find( j ); uf[ fi ] = uf[ fj ]; } } int Find ( int i ) { return (uf[i] == i) ? i : (uf[i] = Find(uf[i]) ); } bool IsSameSet ( int i, int j ) { return Find( i ) == Find( j ); } }; bool Comp ( const Edge & a, const Edge & b ) { return a.w < b.w; } int main() { UnionFind u; int N, M, maxID; LL max; while ( scanf( "%d %d", &N, &M ) == 2 ) { max = 0; FOR(i,0,M) { scanf( "%d %d %lld", &edge[ i ].a, &edge[ i ].b, &edge[ i ].w ); --edge[ i ].a; --edge[ i ].b; if ( edge[ i ].w > max ) { max = edge[ i ].w; maxID = i; } } if ( M == 0 ) { printf( "disconnected\n" ); continue; } edge[ maxID ].w = -edge[ maxID ].w; sort( edge, edge + M, Comp ); LL res = 0; u.Init( N ); FOR(i,0,M) if ( !u.IsSameSet( edge[ i ].a, edge[ i ].b ) ) { u.Union( edge[ i ].a, edge[ i ].b ); res += edge[ i ].w; if ( u.numSets == 1 ) break; } if ( u.numSets == 1 ) printf( "%lld\n", res ); else printf( "disconnected\n" ); } return 0; }
--- c4.s1035.cteam004.spider.cpp.0.spider.cpp +++ c4.s1056.cteam004.spider.cpp.0.spider.cpp @@ -29,5 +29,6 @@ struct Edge { - int a, b, w; + int a, b; + LL w; }; @@ -67,5 +68,6 @@ { UnionFind u; - int N, M, max, maxID; + int N, M, maxID; + LL max; while ( scanf( "%d %d", &N, &M ) == 2 ) { @@ -73,5 +75,5 @@ FOR(i,0,M) { - scanf( "%d %d %d", &edge[ i ].a, &edge[ i ].b, &edge[ i ].w ); + scanf( "%d %d %lld", &edge[ i ].a, &edge[ i ].b, &edge[ i ].w ); --edge[ i ].a; --edge[ i ].b; @@ -91,5 +93,5 @@ sort( edge, edge + M, Comp ); - int res = 0; + LL res = 0; u.Init( N ); FOR(i,0,M) @@ -102,5 +104,5 @@ } if ( u.numSets == 1 ) - printf( "%d\n", res ); + printf( "%lld\n", res ); else printf( "disconnected\n" );