这题把前面两道题组合到了一起 判断最小生成树 和是否是一棵树
#include < iostream > #include < stdio.h > #include < string .h > #include < algorithm > using namespace std; int father[ 101 ]; bool flags[ 101 ]; struct country{ int first; int second; int value;}a[ 5001 ]; bool cmp(country x,country y){ return x.value < y.value;} int makeset( int n){ for ( int i = 1 ;i <= n;i ++ ) father[i] = i;} int findset( int x){ if (father[x] != x) { father[x] = findset(father[x]); } return father[x];} int Union( int a, int b){ int x = findset(a); int y = findset(b); if (x == y) return 1 ; else { father[x] = y; return 0 ; }} int main(){ int n,m; while ( ~ scanf( " %d%d " , & n, & m)) { if (n == 0 ) break ; int sum = 0 ; makeset(m); memset(flags, false , sizeof (flags)); for ( int i = 1 ;i <= n;i ++ ) { scanf( " %d%d%d " , & a[i].first, & a[i].second, & a[i].value); } sort(a + 1 ,a + n + 1 ,cmp); for ( int i = 1 ;i <= n;i ++ ) { if (Union(a[i].first,a[i].second) == 0 ) { sum = sum + a[i].value; } } for ( int i = 1 ;i <= m;i ++ ) { flags[findset(i)] = true ; } int k = 0 ; for ( int i = 1 ;i <= m;i ++ ) { if (flags[i] == true ) k ++ ; } if (k != 1 ) printf( " ?\n " ); else printf( " %d\n " ,sum); } return 0 ;}转载于:https://www.cnblogs.com/cyiner/archive/2011/05/16/2048240.html
