• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            infinity

              C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::
              36 隨筆 :: 0 文章 :: 25 評論 :: 0 Trackbacks
            http://acm.cs.ecnu.edu.cn/problem.php?problemid=2165
            找了個次小生成樹的題目做一做。

            方法是先找出最小生成樹,然后依次添加每條在原圖中,而不在MST上的邊,然后刪除
            形成的環(huán)上的最大邊(先通過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 閱讀(446) 評論(0)  編輯 收藏 引用 所屬分類: acm
            久久经典免费视频| 91精品国产综合久久四虎久久无码一级 | 天天爽天天狠久久久综合麻豆| 精品国产一区二区三区久久| 国产精品99久久久久久人| 热久久国产精品| 国产A级毛片久久久精品毛片| 久久婷婷五月综合97色| 久久国产精品二国产精品| 精品国产99久久久久久麻豆| 91精品国产91久久久久福利| 久久亚洲精品国产亚洲老地址| 国产日产久久高清欧美一区| 色综合久久88色综合天天 | 99久久这里只有精品| 欧美日韩精品久久久免费观看| 久久久久国产一级毛片高清版| 久久亚洲国产精品成人AV秋霞| 中文字幕日本人妻久久久免费| 99久久免费国产精品热| 99精品久久久久久久婷婷| 国产福利电影一区二区三区久久久久成人精品综合 | 很黄很污的网站久久mimi色| 久久久噜噜噜久久中文字幕色伊伊 | 久久久久久a亚洲欧洲aⅴ| 亚洲一区精品伊人久久伊人| 久久免费高清视频| 伊人久久综合无码成人网| 国产AV影片久久久久久| 国产精品久久久久无码av| 欧美牲交A欧牲交aⅴ久久| 国产成人久久精品一区二区三区| 日韩美女18网站久久精品| 久久精品国产一区二区电影| 国产精品久久久久一区二区三区| 97久久超碰国产精品旧版| 亚洲乱码精品久久久久..| 久久婷婷五月综合97色| 国内精品久久久久影院日本| 九九精品99久久久香蕉| 国产精品久久网|