ACM Contest and Blackout Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu
Status
Description
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 Ai, Bi, Ci , where Ci is the cost of the connection (1£Ci£300) between schools Ai and Bi. 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 S1 be the cheapest cost and S2 the next cheapest cost. It’s important, that S1=S2 if and only if there are two cheapest plans, otherwise S1£S2. You can assume that it is always possible to find the costs S1 and S2..
|
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 ; } }
View Code
转载于:https://www.cnblogs.com/hlmark/p/4291464.html
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/109547.html原文链接：https://javaforall.net
