uva 10600 - ACM CONTEST AND BLACKOUT

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

Problem source: Ukrainian National Olympiad in Informatics 2001

Problem author: Shamil Yagiyayev

Problem submitter: Dmytro Chernysh

Problem solution: Shamil Yagiyayev, Dmytro Chernysh, K M Hasan

minimum spanning tree, second minimum spanning tree -find alternative path by replacing any existing edge with sub-optimal one.

#include<stdio.h>
#include<cstring>
#include<queue>
#include<cmath>
#include<vector>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0
#define MAXN 100
#define MAXM 5000
#define INF int(1e9)
using namespace std;

int N,M,e;
int v1[MAXM],v2[MAXM],w[MAXM],p[MAXN],inv[MAXM];
struct Node{
    Node(int ed,int a,int b,int c):e(ed),v1(a),v2(b),dis(c){}
    bool operator <(const Node b)const {return dis>b.dis;}
    int e,v1,v2,dis;
};
void addedge(int a,int b,int c){
    v1[e]=a,v2[e]=b,w[e]=c,e++;
}
int find(int v,int p[]){
    if(p[v]==v)return v;
    return p[v]=find(p[v],p);
}
void unit(int from,int to,int p[]){
    p[find(from,p)]=p[find(to,p)];
}
void ans(){
    int a,b,c,d=0,ce,s1=0,s2=0,m=INF;
    priority_queue<Node>q,q2;
    vector<int>ed;
    rep(i,e)q.push(Node(i,v1[i],v2[i],w[i]));
    q2=q;
    rep(i,N)p[i]=i;
    while(d<N-1){
        ce=q.top().e,a=q.top().v1,b=q.top().v2,c=q.top().dis,q.pop();
        if(DBG)printf("a b %d %d %d\n",a,b,c);
        if(find(a,p)!=find(b,p))unit(a,b,p),ed.push_back(ce),s1+=c,d++;
    }
    rep(i,ed.size()){
        inv[ed[i]]=1;
        q=q2,d=0,s2=0;
        rep(j,N)p[j]=j;
        while(q.size()&&d<N-1){
            ce=q.top().e,a=q.top().v1,b=q.top().v2,c=q.top().dis,q.pop();
            if(!inv[ce]){
                //if(DBG)printf("a b %d %d %d\n",a,b,c);
                if(find(a,p)!=find(b,p))unit(a,b,p),s2+=c,d++;
            }
        }
        if(d==N-1&&s2<m)m=s2;
        inv[ed[i]]=0;
    }
    printf("%d %d\n",s1,m);
}
int main(){
   int a,b,c,n;
   bool ll=0;
   scanf("%d",&n);
   rep(i,n){
        e=0;
        scanf("%d%d",&N,&M);
        rep(i,M)scanf("%d%d%d",&a,&b,&c),a--,b--,addedge(a,b,c);
        ans();
    }
   return 0;
}