spider.cpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
 
int total_length;
bool connected[2001];
 
struct Edge
{
  int v1,v2,l;
  Edge(int from,int to,int length)
  {
    v1=from;v2=to;l=length;
  }
};
 
bool cmpE(const Edge &e1, const Edge &e2)
{
  return e1.l < e2.l;
}
 
vector<Edge> edges;
vector<Edge> tree;
 
void print_edges(const vector<Edge> &edges)
{
  for(int i = 0; i < edges.size(); i++)
    cout << edges[i].l << ',';
  cout << endl;
}
 
void AddToG(const Edge &e)
{
  tree.push_back(e);
  total_length += e.l;
  connected[e.v1] = true;
  connected[e.v2] = true;
}
 
int FindEdge(int vertex)// najdu prvni hranu s timto uzlem k jiz pripojenymu uzlu
{
  for(int i = 0, im = edges.size(); i < im; i++)
  {
    if(edges[i].v1 == vertex)
    {
      if(connected[edges[i].v2])
        return i;
    }
    else if(edges[i].v2 == vertex)
    {
      if(connected[edges[i].v1])
        return i;
    }
  }
  return -1;
}
 
int main()
{
  bool disconnected;
  int N,M,v1,v2,l;
  //
  while(1)
  {
    cin >> N >> M;
    if(cin.eof()) break;
    //
    tree.clear();
    edges.clear();
    memset(connected,0,2001);
    total_length = 0;
    disconnected = false;
    //
    for(int m = 0; m < M; m++)
    {
      cin >> v1 >> v2 >> l;
      edges.push_back(Edge(v1,v2,l));
    }
    sort(edges.begin(),edges.end(),cmpE);
    //
    AddToG(edges[edges.size()-1]);
    //
    for(int n = 1; n <= N; n++) // pro kazdy uzel
    {
      if(connected[n]) continue;
      // najdu prvni hranu s timto uzlem k pripojenymu uzlu
      int ei = FindEdge(n);
      if(ei < 0)
      {
        disconnected = true;
        break;
      }
      AddToG(edges[ei]);
      edges.erase(edges.begin()+ei);
    }
    //
    if(disconnected)
      cout << "disconnected\n";
    else
      cout << (total_length - (2*edges[edges.size()-1].l)) << '\n';
  }
  return 0;
}