spider.cpp
#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, 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, max, maxID;
while ( scanf( "%d %d", &N, &M ) == 2 )
{
max = 0;
FOR(i,0,M)
{
scanf( "%d %d %d", &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 );
int 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( "%d\n", res );
else
printf( "disconnected\n" );
}
return 0;
}