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

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>
            樱花yy私人影院亚洲| 国产精品毛片在线看| 亚洲第一在线视频| 欧美激情影音先锋| 欧美另类女人| 西瓜成人精品人成网站| 午夜欧美不卡精品aaaaa| 国内成+人亚洲| 亚洲黄色av| 欧美日韩亚洲一区二| 久久精品91久久香蕉加勒比| 久久久亚洲精品一区二区三区 | 国产午夜精品理论片a级大结局| 欧美在线观看日本一区| 久色婷婷小香蕉久久| 这里只有精品视频在线| 欧美综合国产| 一本不卡影院| 欧美一区二区三区男人的天堂| 在线看视频不卡| 野花国产精品入口| 在线日本高清免费不卡| 国产精品99久久99久久久二8 | 午夜欧美不卡精品aaaaa| 久久久噜噜噜久久人人看| 中文无字幕一区二区三区| 欧美一区二区三区免费观看| 日韩一级大片| 久久久99爱| 新狼窝色av性久久久久久| 欧美+亚洲+精品+三区| 欧美一区二区在线看| 欧美日韩美女| 亚洲国产精品久久久久秋霞不卡 | 国产精品免费看| 亚洲国产专区校园欧美| 国产亚洲精品久久飘花| 一本色道久久综合狠狠躁篇怎么玩 | 亚洲欧美日韩一区二区在线 | 激情一区二区三区| 亚洲一区日韩在线| 一区二区三区四区在线| 免费成人av在线| 久久亚洲春色中文字幕久久久| 国产精品yjizz| 亚洲丰满在线| 在线不卡中文字幕| 欧美在线观看视频一区二区三区| 亚洲一区二区三区中文字幕| 欧美精品一区二区久久婷婷| 欧美成人69av| 在线观看亚洲精品| 久久久久久网址| 美国三级日本三级久久99| 国产私拍一区| 久久成人在线| 久久久免费av| 在线观看中文字幕不卡| 久久天天躁夜夜躁狠狠躁2022 | 日韩视频免费| 欧美精品日韩| 日韩视频一区二区| 一区二区三欧美| 欧美日韩午夜视频在线观看| 亚洲精品日韩一| 亚洲午夜久久久久久久久电影院 | 夜夜嗨av一区二区三区网页| 91久久综合亚洲鲁鲁五月天| 久久这里有精品视频| 欧美国产日本在线| 91久久精品一区二区别| 免费观看成人| 亚洲麻豆av| 午夜一区在线| 黑丝一区二区三区| 欧美成人免费播放| 亚洲精品小视频| 性欧美8khd高清极品| 国外视频精品毛片| 欧美77777| 99精品国产高清一区二区| 先锋影音国产一区| 影音先锋中文字幕一区| 欧美精品在线一区| 亚洲欧美乱综合| 欧美成人激情视频| 这里只有视频精品| 国产一区二区黄| 欧美大片一区二区三区| 亚洲视频在线观看网站| 久久免费偷拍视频| 99精品99| 国产一区二区三区在线观看视频| 欧美aa国产视频| 午夜精品久久久久久久蜜桃app| 久久综合伊人77777| 亚洲视频一区在线| 激情久久久久久| 欧美视频日韩| 每日更新成人在线视频| 亚洲天堂av电影| 亚洲电影免费观看高清完整版在线观看| 一区二区欧美在线| 精品动漫一区二区| 国产精品日韩一区二区三区| 美女999久久久精品视频| 亚洲视频中文| 亚洲品质自拍| 欧美成人免费网| 欧美在线影院在线视频| 亚洲免费精彩视频| 在线看国产日韩| 国产午夜亚洲精品不卡| 欧美日韩一区二区视频在线观看| 久久这里有精品视频| 欧美一区二区黄| 亚洲一区二区三区四区五区黄| 亚洲国产精品一区二区第一页| 午夜精品久久久久久| 一本色道久久综合精品竹菊| 影音先锋亚洲一区| 国产一区二区三区在线观看免费视频 | 久久中文精品| 久久精品亚洲一区二区三区浴池| 一区二区高清视频| 亚洲精选在线| 亚洲欧洲精品一区| 亚洲福利视频网| 在线免费不卡视频| 影音先锋日韩有码| 黄色资源网久久资源365| 国产一区自拍视频| 国产综合精品一区| 国产在线不卡精品| 韩国三级电影一区二区| 国产又爽又黄的激情精品视频 | 国产噜噜噜噜噜久久久久久久久| 欧美视频中文在线看 | 一区二区三区国产盗摄| 亚洲日本成人网| 亚洲精品一区中文| 99精品视频免费全部在线| 亚洲精品一区二区在线| 99re6这里只有精品视频在线观看| 亚洲国内高清视频| 亚洲三级观看| 一区二区三区视频在线看| 亚洲视频免费看| 小黄鸭精品密入口导航| 久久国产高清| 美脚丝袜一区二区三区在线观看| 男女精品视频| 亚洲人成网站在线播| 日韩视频免费观看高清完整版| 日韩视频在线一区二区| 亚洲影音先锋| 久久九九精品| 欧美大秀在线观看| 欧美性片在线观看| 国产日产亚洲精品| 在线观看欧美一区| 在线视频中文亚洲| 久久黄色小说| 欧美高清视频www夜色资源网| 亚洲人体一区| 午夜在线精品偷拍| 你懂的视频一区二区| 国产精品久久久久久久app| 国内自拍一区| 中日韩高清电影网| 久久天堂av综合合色| 最新日韩在线| 欧美亚洲在线观看| 欧美激情第三页| 国产欧美一区二区三区沐欲 | 久久久不卡网国产精品一区| 亚洲国产欧美久久| 欧美亚洲在线视频| 欧美日韩色一区| 韩日精品视频一区| 亚洲一区二区三区精品视频| 久久亚洲综合| 亚洲专区一区二区三区| 欧美岛国在线观看| 国产一二精品视频| 亚洲天堂av综合网| 欧美激情国产日韩| 午夜精品久久久久| 欧美日韩专区| 亚洲精品日韩在线观看| 久久久精品日韩欧美| 国产精品99久久久久久久女警 | 国内精品久久久久影院色| 亚洲视频你懂的| 亚洲第一网站| 久久婷婷国产综合尤物精品| 国产日韩专区| 性8sex亚洲区入口| 亚洲一品av免费观看| 欧美三级乱码|