UVA 10600 ACM contest and Blackout(次小生成树)

ACM Contest and Blackout Time Limit:3000MS     Memory Limit:0KB     64bit IO Format:%lld & %llu

Submit Status

Description

Problem A

ACM contest and Blackout

In order to prepare the “The First National ACM School Contest”(in 20??) the major of the city decided to provide all the schools with a reliable source of power. (The major is really afraid of blackoutsJ). So, in order to do that, power station “Future” and one school (doesn’t matter which one) must be connected; in addition, some schools must be connected as well.

You may assume that a school has a reliable source of power if it’s connected directly to “Future”, or to any other school that has a reliable source of power. You are given the cost of connection between some schools. The major has decided to pick out two the cheapest connection plans – the cost of the connection is equal to the sum of the connections between the schools. Your task is to help the major – find the cost of the two cheapest connection plans.

Input

The Input starts with the number of test cases, T (1£T£15) on a line. Then T test cases follow. The first line of every test case contains two numbers, which are separated by a space, N (3£N£100) the number of schools in the city, and M the number of possible connections among them. Next M lines contain three numbers A_i, B_i, C_i , where C_i  is the cost of the connection (1£C_i£300) between schools A_i  and B_i. The schools are numbered with integers in the range 1 to N.

Output

For every test case print only one line of output. This line should contain two numbers separated by a single space - the cost of two the cheapest connection plans. Let S₁ be the cheapest cost and S₂ the next cheapest cost. It’s important, that S₁=S₂ if and only if there are two cheapest plans, otherwise S₁£S₂. You can assume that it is always possible to find the costs S₁ and S₂..

Sample Input	Sample Output
2 5 8 1 3 75 3 4 51 2 4 19 3 2 95 2 5 42 5 4 31 1 2 9 3 5 66 9 14 1 2 4 1 8 8 2 8 11 3 2 8 8 9 7 8 7 1 7 9 6 9 3 2 3 4 7 3 6 4 7 6 2 4 6 14 4 5 9 5 6 10	110 121 37 37

裸的次小生成树 ， 要注意下求次小生成树的时候 要符合 ：边数 = 点数 - 1

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>

using namespace std ;
typedef long long LL ;
const int N = 1010;
const int M = 1000010;
struct edge {
    int u , v ,w ;
    bool operator < ( const edge &a ) const {
        return w < a.w ;
    }
}e[M];
int n , m , fa[N] , cnt ;
bool vis[M] ;

int find( int k ) { return k == fa[k] ? k : find(fa[k]); }
int mst( int ban ) {
    int ans = 0 ;
    for( int i = 0 ; i <= n ; ++i ) fa[i] = i ;
    for( int i = 0 ; i <m ; ++i ) {
        int fu = find( e[i].u ) , fv = find( e[i].v );
        if( fu == fv || i == ban ) continue ;
        fa[fv] = fu;
        ans += e[i].w ;
        if( ban == -1 ) vis[i] = true ;
        cnt++ ;
    }
    return ans ;
}

int main () {
    //freopen("in.txt","r",stdin);
    int _ ; cin >> _ ;
    while( _-- ) {    
        cin >> n >> m ;
        for( int i = 0 ; i < m ; ++i ){
            cin >> e[i].u >> e[i].v >> e[i].w ;
        }
        memset( vis , false , sizeof vis ) ;
        sort( e , e + m );
        cout << mst(-1) << ' ' ;
        int ans = (1<<28) ;
        for( int i = 0 ; i < m ; ++i ) if( vis[i] ) {
            cnt = 0 ;
            int tmp = mst(i) ;
            if( cnt == n - 1 ) ans = min( ans , tmp ) ;
        }
        cout << ans << endl ;
    }
}