#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define MAXN 110
#define mmax(a,b) ( (a)> (b)? (a):(b) )
#define mmin(a,b) ( (a)< (b)? (a):(b) )
int n, m;
int map[MAXN][MAXN], cost[MAXN], total;
int pre[MAXN], stack[MAXN], top= 0;
int value[MAXN][MAXN];
bool ok= false;
void prim()
{
bool visite[MAXN];
memset( visite, false, sizeof(visite) );
memset( value, 0, sizeof(value) ); top= 0;
visite[1]= true; total= 0; stack[top++]= 1;
for( int i= 1; i<= n; ++i )
cost[i]= map[1][i], pre[i]= 1;
for( int i= 1; i< n; ++i )
{
int min= INT_MAX, k= -1;
for( int j= 1; j<= n; ++j )
if( !visite[j] && cost[j]>= 0 && cost[j]< min ) min= cost[j],k= j;
for( int j= 0; j< top; ++j )
{
value[ stack[j] ][k]= mmax( value[ pre[k] ][k], min );
value[k][ stack[j] ]= value[ stack[j] ][k];
}
visite[k]= true; total+= min; stack[top++]= k;
for( int j= 1; j<= n; ++j )
if( !visite[j] && map[k][j]>= 0 && ( map[k][j]< cost[j] || cost[j]< 0 ) )
cost[j]= map[k][j], pre[j]= k;
}
}
int secondtree()
{
int m= INT_MAX;
for( int i= 1; i<= n; ++i )
for( int j= 1; j<= n; ++j )
if( i!= j && i!= pre[j] && j!= pre[i] && map[i][j]>= 0 )
m= mmin( m, total- value[i][j]+ map[i][j] );
return m;
}
int main()
{
int test;
scanf("%d",&test);
while( test-- )
{
scanf("%d%d",&n,&m );
for( int i= 0; i<= n; ++i )
for( int j= 0; j<= n; ++j )
map[i][j]= -1;
for( int i= 0; i< m; ++i )
{
int u, v, d;
scanf("%d%d%d",&u,&v, &d );
map[v][u]= d, map[u][v]= d;
}
prim();
int t= secondtree();
if( t== total ) puts("Not Unique!");
else printf("%d\n",total );
}
return 0;
}
posted on 2008-12-06 18:16
Darren 閱讀(424)
評(píng)論(0) 編輯 收藏 引用