infinity

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  36 随笔 :: 0 文章 :: 25 评论 :: 0 Trackbacks
http://acm.cs.ecnu.edu.cn/problem.php?problemid=2165
找了个次小生成树的题目做一做。

方法是先找出最小生成树,然后依次添加每条在原图中,而不在MST上的边,然后删除
形成的环上的最大边(先通过dfs预处理求出MST上任意点之间的最大边权),这样
形成了一棵新树,找出所有添加删除形成的secondary minimum spanning tree就OK了!


#include <stdio.h>
#include
<string.h>
#define INF 2139062143
int m,n,min_dif,flag,lowcost[501],map[501][501],mst_map[501][501],
    s[
501],pre[501],max_val[501][501],vis[501];
void dfs(int sta,int t,int max){
    
for(int i=1;i<=n;i++){
        
if(!vis[i] && mst_map[t][i]!=INF){
            vis[i]
=1;
            
int tmp=max;
            
if(mst_map[t][i]>max) max=mst_map[t][i];
            
if(max>max_val[sta][i]) max_val[sta][i]=max_val[i][sta]=max;
            dfs(sta,i,max);
            max
=tmp;
        }
    }

}
int main(){
    
while(scanf("%d%d",&n,&m)!=EOF){
        memset(map,
127,sizeof(map));
        memset(mst_map,
127,sizeof(mst_map));
        memset(lowcost,
127,sizeof(lowcost));
        memset(s,
0,sizeof(s));
        memset(pre,
0,sizeof(pre));
        memset(max_val,
128,sizeof(max_val));
        
int i,j,idx,min_mst=0,mincost,a,b,c;
        
for(i=1;i<=m;i++){
            scanf(
"%d%d%d",&a,&b,&c);
            map[a][b]
=map[b][a]=c;
        }
        
//prim algorithm
        lowcost[1]=0;
        
for(i=1;i<=n;i++){
            mincost
=INF;
            
for(j=1;j<=n;j++)
                
if(!s[j] && lowcost[j]<mincost){
                    mincost
=lowcost[j];
                    idx
=j;
                }
            s[idx]
=1;
            min_mst
+=mincost;
            mst_map[idx][pre[idx]]
=mst_map[pre[idx]][idx]=map[pre[idx]][idx];
            
for(j=1;j<=n;j++){
                
if(!s[j] && map[idx][j]<lowcost[j]){
                    lowcost[j]
=map[idx][j];
                    pre[j]
=idx;
                }
            }
        }
        
//calc max_val[i][j] 
        for(i=1;i<=n;i++){
            memset(vis,
0,sizeof(vis));
            vis[i]
=1;
            dfs(i,i,
-INF);
        }
        
//for each edge excluded int the MST
        
//try to get secondary minimum spanning tree
        min_dif=INF;flag=0;
        
for(i=1;i<=n;i++){
            
for(j=i+1;j<=n;j++){
                
if(mst_map[i][j]==INF && map[i][j]!=INF){
                    flag
=1;//mark if there's s new tree
                    if(map[i][j]-max_val[i][j]<min_dif) min_dif=map[i][j]-max_val[i][j];
                }
            }    
        }
        
if(!flag) printf("%d -1\n",min_mst);
        
else printf("%d %d\n",min_mst,min_mst+min_dif);
    }
    
return 0;
}


posted on 2008-11-17 01:38 infinity 阅读(287) 评论(0)  编辑 收藏 引用 所属分类: acm

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理