Dowemo

topic description

time limit: 600 ms memory limit: 8000 kb
ea 's simulated business class game"", it's a lot of people to play. ~.
jeffrey like to play, but it doesn't mean he is a good player. jeffrey 's is now, because it's simple: he's.!
, now he wants to keep some road, remove the rest of the road, demand to keep each area of the city connected to each other, making the road maintenance minimum.
in order to simplify the problem, assume that all road lengths are maintained for 1. data guarantees that the entire is a connected graph.

enter

multiple test data. each group of data is two integers, representing a, range, m road. ( 1 ≤n≤10^3, 0 ≤m≤10^5 )
the next m line, three integer u, v, l, representing a two-way road between region u and region v. ( 1 ≤u, v≤n, 1 ≤l≤100 )

output

for each group of data, the minimum total maintenance maintenance costs.

enter sample


6 10


1 2 6


1 3 1


1 4 5


2 3 5


2 5 3


3 4 5


3 5 6


3 6 4


4 6 2


5 6 6






sample sample


15






prim + heap optimization

#include <cstdio>


#include <queue>


#include <vector>


#include <cstring>


using namespace std;


typedef long long ll;


struct mstNode{


 int head;


 int tail;


 int weight;


 mstNode(int h=-1,int t=-1,int w=-1):head(h),tail(t),weight(w){}


 bool operator> (const mstNode& p) const {


 return weight>p.weight;


 }


};


struct node{


 int rank;


 int weight;


 node(int r=-1,int w=-1):rank(r),weight(w){}


};


int n,m;


ll sum;


vector<node> matrix[1001];


vector<mstNode> msTree;


inline void prim(int v0){


 int v,count;


 mstNode selected;


 priority_queue<mstNode,vector<mstNode>,greater<mstNode>> minHeap;


 bool vOfmst[n+1];


 memset(vOfmst,0,sizeof(vOfmst));


 vOfmst[v0]=true;


 count=1;


 v=v0;


 while(count<n){


 for(int i=0,size=(int)matrix[v].size();i<size;++i)


 if(!vOfmst[matrix[v][i].rank])


 minHeap.push(mstNode(v,matrix[v][i].rank,matrix[v][i].weight));


 again:


 selected=minHeap.top();minHeap.pop();


 if(!vOfmst[selected.tail]){


 msTree.push_back(selected);


 ++count;


 vOfmst[selected.tail]=true;


 }else goto again;


 v=selected.tail;


 }


 sum=0;


 for(int i=0,size=(int)msTree.size();i<size;++i)


 sum+=msTree[i].weight;


}


int main(){


 int u,v,w;


 while(~scanf("%d%d",&n,&m)){


 for(int i=0;i<m;++i){


 scanf("%d%d%d",&u,&v,&w);


 matrix[u].push_back(node(v,w));


 matrix[v].push_back(node(u,w));


 }


 prim(1);



 printf("%lldn",sum);


 msTree.clear();


 for(int i=1;i<=n;i++)


 matrix[i].clear();


 }


}






group

#include <cstdio>


#include <algorithm>


#define MAXN 100005


using namespace std;


int num_V,num_E,ans;



struct Node{


 int to,from,cost;


}road[MAXN];


int Par[MAXN];



bool cmp(const Node &a,const Node &b){


 return (a.cost<b.cost);


}



void init(){


 for(int i=0;i<num_E;i++) Par[i]=-1;


}



int Find(int x){


 int root=x;


 while(Par[root]>=0) root=Par[root];


 return root;


}



void unite(int x,int y){


 x=Find(x); y=Find(y);


 if(Par[x]<Par[y]){


 Par[x]+=Par[y];


 Par[y]=x;


 }


 else{


 Par[y]+=Par[x];


 Par[x]=y;


 }


}



int Kruskal(){


 int nEdge=0,fees=0;


 for(int i=0;i<num_E&&nEdge!=num_V-1;i++){


 if(Find(road[i].from)!=Find(road[i].to)){


 unite(road[i].from,road[i].to);


 fees+=road[i].cost;


 nEdge++;


 }


 }


 return fees;


}



int main(){


 while(~scanf("%d%d",&num_V,&num_E)){


 init();


 for(int i=0;i<num_E;i++){


 scanf("%d%d%d",&road[i].from,&road[i].to,&road[i].cost);


 }


 sort(road,road+num_E,cmp);


 ans=Kruskal();


 printf("%dn",ans);


 }


}









Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs