青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

POJ 3164 Command Network 最小樹形圖

Description

After a long lasting war on words, a war on arms finally breaks out between littleken’s and KnuthOcean’s kingdoms. A sudden and violent assault by KnuthOcean’s force has rendered a total failure of littleken’s command network. A provisional network must be built immediately. littleken orders snoopy to take charge of the project.

With the situation studied to every detail, snoopy believes that the most urgent point is to enable littenken’s commands to reach every disconnected node in the destroyed network and decides on a plan to build a unidirectional communication network. The nodes are distributed on a plane. If littleken’s commands are to be able to be delivered directly from a node A to another node B, a wire will have to be built along the straight line segment connecting the two nodes. Since it’s in wartime, not between all pairs of nodes can wires be built. snoopy wants the plan to require the shortest total length of wires so that the construction can be done very soon.

Input

The input contains several test cases. Each test case starts with a line containing two integer N (N ≤ 100), the number of nodes in the destroyed network, and M (M ≤ 104), the number of pairs of nodes between which a wire can be built. The next N lines each contain an ordered pair xi and yi, giving the Cartesian coordinates of the nodes. Then follow M lines each containing two integers i and j between 1 and N (inclusive) meaning a wire can be built between node i and node j for unidirectional command delivery from the former to the latter. littleken’s headquarter is always located at node 1. Process to end of file.

Output

For each test case, output exactly one line containing the shortest total length of wires to two digits past the decimal point. In the cases that such a network does not exist, just output ‘poor snoopy’.

Sample Input

4 6
0 6
4 6
0 0
7 20
1 2
1 3
2 3
3 4
3 1
3 2
4 3
0 0
1 0
0 1
1 2
1 3
4 1
2 3

Sample Output

31.19
poor snoopy

Source


 

最小樹形圖算法(Zhu-Liu Algorithm)

1.       設(shè)最小樹形圖的總權(quán)值為cost,置cost0

2.       除源點(diǎn)外,為其他所有節(jié)點(diǎn)Vi找一條權(quán)值最小的入邊,加入集合TT就是最短邊的集合。加邊的方法:遍歷所有點(diǎn)到Vi的邊中權(quán)值最小的加入集合T,記pre[Vi]為該邊的起點(diǎn),mincost[Vi]為該邊的權(quán)值。

3.       檢查集合T中的邊是否存在有向環(huán),有則轉(zhuǎn)到步驟4,無則轉(zhuǎn)到步驟5。這里需要利用pre數(shù)組,枚舉檢查過的點(diǎn)作為搜索的起點(diǎn),類似dfs的操作判斷有向環(huán)。

4.       將有向環(huán)縮成一個(gè)點(diǎn)。設(shè)環(huán)中有點(diǎn){Vk1,Vk2,…,Vki}i個(gè)點(diǎn),用Vk代替縮成的點(diǎn)。在壓縮后的圖中,更新所有不在環(huán)中的點(diǎn)VVk的距離:

map[V][Vk] = min {map[V][Vkj]-mincost[Vki]} 1<=j<=i

map[Vk][V] = min {map[Vkj][V]}           1<=j<=I

5.       cost加上T中有向邊的權(quán)值總和就是最小樹形圖的權(quán)值總和。

#include <iostream>
#include 
<cmath>

#define min(a,b) (a<b ? a:b)

const int MAXN = 110;
const int INF = 0x7FFFFFFF;
int n,m,pre[MAXN];
double x[MAXN],y[MAXN];
bool circle[MAXN],visit[MAXN];
double ans,map[MAXN][MAXN];

inline 
double distance(double x1,double y1,double x2,double y2){
    
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

void dfs(int u){
    visit[u]
=true;
    
for(int i=2;i<=n;i++)
        
if(!visit[i] && map[u][i]!=INF)
            dfs(i);
}

bool connected(){
    memset(visit,
false,sizeof(visit));
    
int i,cnt=0;
    
for(i=1;i<=n;i++)
        
if(!visit[i])
            dfs(i),cnt
++;
    
return cnt==1 ? true : false;
}

void min_arborescence(){
    
int i,j,k;
    memset(circle,
false,sizeof(circle));
    
while(true){
        
for(i=2;i<=n;i++){
            
if(circle[i]) continue;
            pre[i]
=i;
            map[i][i]
=INF;
            
for(j=1;j<=n;j++){
                
if(circle[j]) continue;
                
if(map[j][i]<map[pre[i]][i])
                    pre[i]
=j;
            }

        }

        
for(i=2;i<=n;i++){
            
if(circle[i]) continue;
            j
=i;
            memset(visit,
false,sizeof(visit));
            
while(!visit[j] && j!=1){
                visit[j]
=true;
                j
=pre[j];
            }

            
if(j==1continue;
            i
=j;
            ans
+=map[pre[i]][i];
            
for(j=pre[i];j!=i;j=pre[j]){
                ans
+=map[pre[j]][j];
                circle[j]
=true;
            }

            
for(j=1;j<=n;j++){
                
if(circle[j]) continue;
                
if(map[j][i]!=INF)
                    map[j][i]
-=map[pre[i]][i];
            }

            
for(j=pre[i];j!=i;j=pre[j])
                
for(k=1;k<=n;k++){
                    
if(circle[k]) continue;
                    map[i][k]
=min(map[i][k],map[j][k]);
                    
if(map[k][j]!=INF)
                        map[k][i]
=min(map[k][i],map[k][j]-map[pre[j]][j]);
                }

            
break;
        }

        
if(i>n){
            
for(j=2;j<=n;j++){
                
if(circle[j]) continue;
                ans
+=map[pre[j]][j];
            }

            
break;
        }

    }

}

int main(){
    
int i,j,u,v;
    
while(scanf("%d %d",&n,&m)!=EOF){
        
for(ans=i=0;i<=n;i++for(j=0;j<=n;j++) map[i][j]=INF;
        
for(i=1;i<=n;i++) scanf("%lf %lf",&x[i],&y[i]);
        
while(m--){
            scanf(
"%d %d",&u,&v);
            map[u][v]
=distance(x[u],y[u],x[v],y[v]);
        }

        
if(!connected()) puts("poor snoopy");
        
else{
            min_arborescence();
            printf(
"%.2lf\n",ans);
        }

    }

    
return 0;
}

posted on 2009-05-26 16:03 極限定律 閱讀(687) 評(píng)論(0)  編輯 收藏 引用 所屬分類: ACM/ICPC

<2009年5月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(10)

隨筆分類

隨筆檔案

友情鏈接

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲青色在线| 亚洲国产精品一区二区三区| 亚洲欧美日韩爽爽影院| 欧美视频二区| 性久久久久久久| 久久超碰97中文字幕| 在线观看欧美| 亚洲裸体视频| 国产无遮挡一区二区三区毛片日本| 久久久久国内| 欧美ed2k| 亚洲一区二区免费在线| 欧美在线视频免费| 亚洲经典三级| 亚洲宅男天堂在线观看无病毒| 国产精品一区二区三区乱码| 久久综合给合| 欧美日韩午夜| 久久综合99re88久久爱| 欧美日韩在线观看视频| 久久久久久一区二区| 欧美激情偷拍| 久久久99国产精品免费| 欧美日本一道本在线视频| 久久国产婷婷国产香蕉| 欧美国产精品劲爆| 久久精品盗摄| 欧美午夜理伦三级在线观看| 欧美 日韩 国产 一区| 国产精品99一区| 欧美黄色免费网站| 国产一区二区激情| 99这里只有精品| 亚洲国产美女| 久久精品国产77777蜜臀| 一区二区电影免费观看| 久久综合九色综合久99| 欧美一区二区在线播放| 欧美人妖在线观看| 欧美高清免费| 极品尤物久久久av免费看| 一区二区三区日韩在线观看| 亚洲精品国产精品乱码不99| 久久狠狠亚洲综合| 欧美在线一二三四区| 国产精品高潮久久| 亚洲精品资源| 99精品国产一区二区青青牛奶| 久久人人97超碰国产公开结果 | 亚洲欧美国产日韩天堂区| 免费在线观看一区二区| 男人插女人欧美| 狠狠网亚洲精品| 欧美在线观看网址综合| 久久精品日韩欧美| 国产精品在线看| 亚洲系列中文字幕| 亚洲欧美在线aaa| 国产精品va在线播放我和闺蜜| 日韩网站免费观看| av成人免费观看| 欧美男人的天堂| 亚洲每日在线| 一区二区三区四区国产精品| 欧美日韩国产色视频| 亚洲人成在线影院| 一本久久a久久免费精品不卡| 欧美激情第1页| 亚洲免费观看| 亚洲欧美日韩国产| 国产日韩欧美自拍| 久久久久国产精品厨房| 欧美va亚洲va国产综合| 亚洲精品黄网在线观看| 欧美另类在线播放| 亚洲视频1区| 久久久久久成人| 亚洲东热激情| 欧美美女bb生活片| 亚洲无限av看| 久久―日本道色综合久久| 亚洲国产精品尤物yw在线观看 | 午夜精彩视频在线观看不卡| 久久久久9999亚洲精品| 最新中文字幕亚洲| 国产精品久久999| 久久成人精品电影| 91久久国产精品91久久性色| 亚洲女同精品视频| 在线成人国产| 欧美视频亚洲视频| 久久国产欧美| 日韩视频在线一区二区三区| 久久av一区二区| 亚洲欧洲美洲综合色网| 国产精品高清在线观看| 久久久久.com| 99视频在线精品国自产拍免费观看| 欧美一区影院| 日韩天堂av| 国产亚洲女人久久久久毛片| 欧美激情网站在线观看| 欧美一区二区三区四区视频| 亚洲人成人一区二区在线观看| 欧美有码在线视频| 夜夜嗨av一区二区三区网页| 国产午夜精品久久久| 欧美日韩精品欧美日韩精品一| 欧美在线视频免费播放| 亚洲一级特黄| 亚洲日本成人在线观看| 久热爱精品视频线路一| 午夜日韩在线| 一区二区三区高清在线| 一区二区在线不卡| 国产日韩av在线播放| 欧美日韩精品一二三区| 美女主播视频一区| 久久久精品tv| 欧美一区二区三区播放老司机| 99国产精品久久久久久久久久| 欧美.www| 蜜臀a∨国产成人精品| 欧美亚洲网站| 亚洲免费在线视频| 99国产精品久久久久久久久久 | 国产农村妇女精品一区二区| 欧美日韩亚洲一区二区三区在线观看 | 欧美不卡高清| 久久琪琪电影院| 久久狠狠亚洲综合| 欧美一级电影久久| 午夜精品久久久久久久99热浪潮| 日韩一级精品视频在线观看| 亚洲国产一区二区三区在线播| 免费视频一区| 欧美xart系列高清| 免费亚洲一区二区| 欧美激情一区二区久久久| 欧美成人精品一区| 亚洲成在线观看| 欧美激情91| 亚洲黄色av| 日韩一区二区精品葵司在线| 日韩一级免费观看| 在线视频日韩| 午夜国产精品视频免费体验区| 亚洲欧美视频一区二区三区| 亚洲欧美经典视频| 欧美在线视频观看| 免费成人av| 欧美破处大片在线视频| 国产精品国产成人国产三级| 国产欧美一区二区精品忘忧草| 国产婷婷色一区二区三区在线 | 亚洲一区精品电影| 欧美一区二区三区免费大片| 欧美一区网站| 欧美v国产在线一区二区三区| 亚洲激情成人| 在线天堂一区av电影| 性色av一区二区三区红粉影视| 久久经典综合| 欧美理论电影在线观看| 国产精品久久久久久久久搜平片 | 91久久夜色精品国产网站| 一区二区电影免费在线观看| 午夜欧美精品久久久久久久| 久久久久综合网| 欧美日韩专区| 狠狠爱成人网| 一区二区三区欧美亚洲| 久久久91精品国产| 最近中文字幕日韩精品| 亚洲欧美在线网| 欧美大片在线观看一区二区| 国产精品丝袜xxxxxxx| 亚洲大胆av| 亚洲欧美视频在线观看视频| 免费欧美网站| 亚洲专区国产精品| 欧美高清视频在线| 国产日韩在线视频| 一本到高清视频免费精品| 久久九九精品| 国产精品99久久99久久久二8| 久久久久国产一区二区| 国产精品久久久久9999吃药| 亚洲黄网站在线观看| 欧美一区二区在线免费观看| 亚洲国产精品一区二区久| 欧美在线999| 国产精品专区h在线观看| 日韩网站在线观看| 老司机免费视频一区二区| 亚洲一级一区| 欧美午夜性色大片在线观看| 亚洲激情一区二区| 免费一级欧美片在线播放| 性欧美video另类hd性玩具|