spider.cpp
#include <cstdio>
#include <string>
#include <set>
#include <vector>
#include <queue>
#include <utility>
#include <map>
using namespace std;
class mycmp{
public:
bool operator()( const pair<int,int> & lhs, const pair<int,int> & rhs ) const{
return (lhs.first-rhs.first)>0;
}
};
int main(void){
int nodeNO, linkNO;
while (scanf("%d %d", &nodeNO, &linkNO)==2){
int len =0;
set<int> Set;
set<int> Set2;
multimap<int, pair<int,int> > mmp;
priority_queue<pair<int,int>, vector<pair<int,int> >, mycmp> pq; ////
pair<int,pair<int,int> > max = make_pair(0, make_pair(0,0));
for (int i=0; i < linkNO; i++){
int u,v,l;
scanf("%d %d %d",&u, &v,&l);
pair<int,pair<int,int> > tmp = make_pair(l, make_pair(u,v));
Set2.insert(u);
Set2.insert(v);
if (l>max.first){
if (max.first>0)
{
mmp.insert(make_pair(max.second.second,make_pair(max.first,max.second.first)));
mmp.insert(make_pair(max.second.first,make_pair(max.first,max.second.second)));
}
max = tmp;
}else {
mmp.insert(make_pair(v,make_pair(l,u)));
mmp.insert(make_pair(u,make_pair(l,v)));
}
}
Set.insert(max.second.first);
Set.insert(max.second.second);
len -= max.first;
multimap<int,pair<int,int> >::iterator it;
while ((it = mmp.find(max.second.first))!=mmp.end()){
// printf("it+=<%d,%d> \n", it->second.first, it->second.second);
pq.push(it->second);
mmp.erase(it);
}
while ((it = mmp.find(max.second.second))!=mmp.end()){
// printf("it*=<%d,%d> \n", it->second.first, it->second.second);
pq.push(it->second);
mmp.erase(it);
}
while (!pq.empty()){
pair<int,int> tm = pq.top();
pq.pop();
// printf("tm=<%d,%d> \n",tm.first, tm.second);
if (Set.find(tm.second) == Set.end()){
// printf("len = %d ; new len = %d; tm = %d\n", len , len +tm.first, tm.first);
len += tm.first;
Set.insert(tm.second);
while ((it = mmp.find(tm.second))!=mmp.end()){
// printf("it=<%d,%d> \n", it->second.first, it->second.second);
pq.push(it->second);
mmp.erase(it);
}
}
}
if (!mmp.empty() || ((int)Set2.size())< nodeNO)
printf("disconnected\n");
else
printf("%d\n",len);
}
return 0;
}