spider.cpp
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<list>
#include<stack>
#include<queue>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define PB push_back
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define fi first
#define se second
#define SIZE(s) (int) (s).size()
#define INF 987654321
#define ll long long
//----------------------
#define MAX 2047
int N, M;
int dad[MAX];
void make_set(int x)
{
dad[x] = -1;
}
int find_set(int x)
{
int k,i=x;
while(dad[i]>=0)
i = dad[i];
while(dad[x]>=0)
{
k=dad[x];
dad[x]=i;
x=k;
}
return x;
}
void union_set(int x, int y)
{
int sx=find_set(x), sy=find_set(y);
if (sx!=sy)
{
if (dad[sx]<dad[sy])
{
dad[sx]+=dad[sy];
dad[sy]=sx;
}
else
{
dad[sy]+=dad[sx];
dad[sx]=sy;
}
}
}
bool discon()
{
int root = find_set(0);
FOR(i,1,N-1)
if (find_set(i) != root)
return true;
return false;
}
vector< pair<int, PII> > hrany;
int main()
{
int a, b, d, max_a=-1, max_b=-1, max_d;
while(scanf("%d %d",&N,&M)==2)
{
hrany.clear();
max_d = -1;
FOR(i,0,M-1)
{
scanf("%d %d %d",&a,&b,&d);
a--; b--;
hrany.PB( MP(d, MP(a,b)) );
if (d > max_d)
{
max_d = d;
max_a = a;
max_b = b;
}
}
sort(hrany.begin(),hrany.end());
/*
FOR(i,0,M-1)
{
cout << hrany[i].fi << " " << hrany[i].se.fi << " " << hrany[i].se.se << endl;
}
*/
FOR(i,0,N-1)
make_set(i);
union_set(max_a, max_b);
int sum = -max_d;
FOR(i,0,M-1)
{
pair< int, PII > h = hrany[i];
if (find_set(h.se.fi) != find_set(h.se.se))
{
union_set(h.se.fi, h.se.se);
sum+= h.fi;
}
}
if (discon())
printf("disconnected\n");
else
printf("%d\n",sum);
}
return 0;
}