myhalfsea's Blog
Happy coding
UESTC 并查集
| Earthquake Time Limit:2000ms Memory Limit: 65535K Submited:652 Accepted:216 Cached at 2010/5/2 22:00:18 |
||
| Description | ||
| After the big earthquake, a lot of roads have been destroyed, some towns are disconnected with each other. In order to save the trapped as soon as possible, we need to try our best to rebuild the roads, and make sure all the towns will be reconnected(that is any villages is connected to the others with a clear route at least). Unfortunately, we have only one team to rebuild the roads. Now,please tell us how long do you think these roads can be reconnected. |
||
| Input | ||
| The first line contains a number T denotes the number of test case. For each test case, In the first line, you will get two number N (1<=N<=1000) and M(1<=M<=N*N), denotes the number of towns and the number of roads. The next M lines, each contains three number A,B,C, denotes there is a road between A and B that needed C (1<=C<=1000) minutes to rebuild. |
||
| Output | ||
| For each test case, you should output a line contains a number denotes the minimal time need to rebuild the roads so that all the towns are connected. | ||
| Sample Input | ||
| 2 3 3 1 2 3 2 3 3 3 1 7 3 3 1 2 3 2 3 3 3 1 1 |
||
| Sample Output | ||
|
6 |
#include <iostream>
#include <string>
#include<algorithm>
using namespace std;
class node{
public:
int a, b, c;
};
bool cmp(node x, node y){
return x.c < y.c;
}
node p[1000005];
bool mark[1010];
int rank[1002];
int parent[1002];
int Find(int x){
if( x != parent[x] )
parent[x] = Find(parent[x]);
return parent[x];
}
void Union(int root1, int root2){
int x = Find(root1), y = Find(root2);
if( x == y ) return ;
if( rank[x] > rank[y] ) parent[y] = x;
else{
parent[x] = y;
if( rank[x] == rank[y] ) ++rank[y];
}
}
void initi(void){
memset(rank, -1, sizeof(rank));
for( int i=0; i < 1001; ++i ) parent[i] = i;
}
void hexie( void ){
int n, m;
int i, res, k;
scanf( "%d %d", &n, &m );
initi();
for( i = 0; i < m; i++ )
scanf( "%d %d %d", &p[i].a, &p[i].b, &p[i].c );
sort(p, p+m, cmp);
res = k = 0;
for( i = 0; i < m; i++ ) {
if( Find(p[i].a) != Find(p[i].b) ) {
Union(p[i].a, p[i].b);
res += p[i].c;
++k;
if( k == m-1 ) break;
}
}
printf("%d\n", res);
}
int main()
{
int t;
scanf("%d", &t);
while( t-- )
hexie();
return 0;
}
评论 (0)
Butterfly Theme | Design: HRS Hersteller of mobile Hundeschule.