POJ 1679 The Unique MST

这是一个次小生成树的题目，我们知道要求最小生成树的方法，次小生成树在最小生成树的基础上运算就可以了，这里采用最简单的方法就是去掉最小生成树集合当中的每一条边再做kruskal,每次kruskla的时间复杂度有mlogm+m,进行最小生成树中边集的枚举复杂度为(n-1)*(m*logm+m),这题还是做到的，还有一种更好的方法，只要做一次kruskal就好了，实现起来有点复杂。

先贴本题的代码：

[cpp] 
#include<iostream> 
#include<algorithm> 
#define maxn 105 
#define maxe 5050 
using namespace std; 
struct Edge 
{ 
       int a,b,w,flag; 
} e[maxe]; 
int n,m,c; 
int f[maxn],used[maxn]; 
void Set() 
{ 
     for(int i=1; i<=n; i++){ 
          f[i]=i; 
     } 
} 
int Find(int x) 
{ 
     if( x!=f[x]) 
         f[x]=Find(f[x]); 
     return f[x]; 
} 
bool cmp(Edge a,Edge b) 
{ 
      return a.w<b.w;  
} 
int Kruskal() 
{ 
    int i,x,y,ret; 
    ret=0; c=0; 
    Set(); 
    for( i=0; i<m&&c<n-1; i++){ 
         x=Find(e[i].a); 
         y=Find(e[i].b); 
         if( x==y) continue; 
         f[x]=y; 
         ret+=e[i].w; 
         used[c++]=i;  
    } 
    return (c<n-1? 0:ret);          
} 
int SecKruskal() 
{ 
    int i,x,y,ret,count; 
    ret=0; count=0; 
    Set(); 
    for( i=0; i<m&&count<n-1; i++){ 
         x=Find(e[i].a); 
         y=Find(e[i].b); 
         if( x==y|| e[i].flag) continue; 
         f[x]=f[y]; 
         ret+=e[i].w; 
         count++;  
    } 
    return ( count<n-1? 0:ret);          
} 
     
int main() 
{ 
    int t,mst,smst,pt,i; 
    scanf("%d",&t); 
    while( t--){ 
           scanf("%d%d",&n,&m); 
           memset(e,0,sizeof(e));  
           memset(used,0,sizeof(used)); 
           memset(f,0,sizeof(f)); 
           for( i=0; i<m; i++) 
                scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].w);      
           sort(e,e+m,cmp);    //按边值大小排序  
            
           mst=Kruskal();    //第一次kruskal求最小生成树 mst  
            
           pt=0;  //最小生成树不同至少要有一条边不同。  
           for( i=0; i<c; i++){ 
                e[used[i]].flag=1; 
                smst=SecKruskal(); 
                e[used[i]].flag=0; 
                if( smst==mst&&smst!=0){   //如果最小树不是唯一的。 
                    pt=1; 
                    break; 
                }   
           }     
           if( pt) 
               printf("Not Unique!\n"); 
           else 
               printf("%d\n",mst);     
    } 
    return 0;  
} 

补充：软件开发 , C++ ,

上一个：C++编码中减少内存缺陷的方法和工具
下一个：HDU 2768 Cat vs Dog(最大独立集)