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;
}