原来POJ上也有这么多水题,连续三道裸的最小生成树了。
View Code
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm> using namespace std; struct node { int a, b, num; bool operator < ( const node& A) const { return num < A.num; } }edge[4100000]; int N, e, set[2100], mp[510][510]; int find( int x ) { return x == set[x] ? x : set[x] = find(set[x]); } void merge( int x, int y) { set[x] = y; } void Krusal( ) { int sum = 0; sort( edge, edge + e); for( int i = 0; i < e; i++) { int x = find(edge[i].a); int y = find(edge[i].b); if( x != y ) { merge(x, y); //if( edge[i].num > sum ) sum += edge[i].num; } } printf("%d\n",sum); } int main( ) { while( scanf("%d",&N) != EOF ) { e = 0; for( int i = 1; i <= N; i++) { set[i] = i; } for( int i = 1; i <= N; i++) for( int j = 1; j <= N; j++) scanf("%d",&mp[i][j]); for( int i = 1; i <= N; i++) { for( int j = 1; j <= i; j++) { if( i != j ) { edge[e].a = i; edge[e].b = j; edge[e++].num = mp[i][j]; } } } Krusal(); } return 0; }