Problem地址:http://acm.hdu.edu.cn/showproblem.php?pid=3367
如果懂一点并查集或Kruskal算法的话,这题并不算很难。题目求的是“伪森林”,也就是一颗或多颗”伪树“的集合(不知道是不是真有“伪树”这定义,我简单搜了一下,好像没有,这里的“伪树”就是指最多带一个环的树)。我刚开始用Kruskal直接生成一棵“最大生成树”,然后再从没有选用的边中选一条最大的边加上。这里事实上就是没有理清题意。所以不能采用这种思路,因为这里可能有多颗”伪树“。
那么这题就可以这么做:先将各边递减排序,然后依次选最大的边,这时要将各边合成成树,如果两颗树都是有环的,那么就不能继续合并,因为这样子合并的图就有两个环了,不符合题目给的定义;如果两颗树中只有一个有环或都没有环,则合并。如何知道每个点所处的图是否有环呢?就像每个图都有一个”根节点“,可以对这个点进行标记是否有环。
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; typedef struct Edge{ int from, to, len; // 某条边的 起点,终点,长度 }Edge; const int MAXN = 10000 + 50; int used[MAXN]; // 记录"根结点" bool hasLoop[MAXN]; // 记录是否有环 Edge edge[MAXN*10]; bool cmp( Edge a, Edge b ) { // 用于sort排序 return a.len > b.len; } void Init( int N ) { // 初始化 for( int i=0; i<N; i++ ) { used[i] = i; } memset( hasLoop, false, sizeof(hasLoop) ); } int Find( int N ) { // 查找并同时更新 if( used[N] == N ) { return N; } used[N] = Find( used[N] ); hasLoop[ N ] = hasLoop[ used[N] ]; return used[N]; } int KruskalAndModi( int N, int M ) { int length = 0; sort( edge, edge+M, cmp ); int fRoot, tRoot; for( int i=0; i<M; i++ ) { fRoot = Find( edge[i].from ); tRoot = Find( edge[i].to ); if( fRoot == tRoot ) { // 处在同一图中 if( !hasLoop[fRoot] ) { // 如果没有环,则继续,可以形成一个环 length += edge[i].len; hasLoop[ fRoot ] = true; } } else { if( hasLoop[fRoot]&&hasLoop[tRoot] ) { // 都有环,不做处理 continue; } else if( hasLoop[ fRoot ] || hasLoop[tRoot] ) { // 其中一个有环,合并后成为一有环的图 hasLoop[ fRoot ] = hasLoop[tRoot] = true; } // 省略了以一些判断,因为有些操作是相同的 used[ fRoot ] = tRoot; length += edge[i].len; } } return length; } int main() { int N, M; int i; while( scanf( "%d%d", &N, &M )!=EOF ) { if( N==M && M==0 ) { break; } Init( N ); int f, t ,s; for( i=0; i<M; i++ ) { scanf( "%d%d%d", &f, &t, &s ); edge[i].from = f; edge[i].to = t; edge[i].len = s; } printf( "%d ", KruskalAndModi( N, M ) ); } return 0; }