频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
POJ 1679 The Unique MST
2012-07-18 14:03:16           
收藏   我要投稿

这是一个次小生成树的题目,我们知道要求最小生成树的方法,次小生成树在最小生成树的基础上运算就可以了,这里采用最简单的方法就是去掉最小生成树集合当中的每一条边再做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;  


作者:aacm1992
点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:HDU 2768 Cat vs Dog(最大独立集)
下一篇:C++编码中减少内存缺陷的方法和工具
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站