畅通工程
最小生成树,通过统计连通路的个数和总路数比较,来判断是否所有的路径都已经连通了,需要注意的是这里sum应该从1 开始,因为一开始就是从某一条路出发的
// File Name: hdu1863.cpp // Author: rudolf // Created Time: 2013年04月27日 星期六 15时21分31秒 #include<vector> #include<list> #include<map> #include<set> #include<deque> #include<stack> #include<bitset> #include<algorithm> #include<functional> #include<numeric> #include<utility> #include<sstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<ctime> using namespace std; const int maxn=10005; int fa[105]; struct node { int x,y,value; }edge[maxn]; int find( int x ) { return fa[ x ] = x == fa[ x ]? x : find( fa[ x ] ); } int cmp( const node a, const node b ) { return a.value < b.value; } int main() { int m,n; int i; while(cin>>n>>m) { if( n == 0 ) break; for( i = 1; i <= m; i++ ) fa[ i ] = i; for( i = 1; i <= n; i++ ) { cin>>edge[i].x>>edge[i].y>>edge[i].value; } sort( edge + 1 , edge + n + 1, cmp ); int ans = 0; int sum=1; for( i = 1;i <= n; i++ ) { int x1 = find( edge[ i ].x ); int x2 = find( edge[ i ].y ); if( x1 != x2 ) { fa[ x1 ] = x2; ans += edge[ i ].value; sum++; } } if( sum == m ) cout<<ans<<endl; else cout<<"?"<<endl; } return 0; }