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

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.       設最小樹形圖的總權值為cost,置cost0

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

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

4.       將有向環(huán)縮成一個點。設環(huán)中有點{Vk1,Vk2,…,Vki}i個點,用Vk代替縮成的點。在壓縮后的圖中,更新所有不在環(huá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中有向邊的權值總和就是最小樹形圖的權值總和。

#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) 評論(0)  編輯 收藏 引用 所屬分類: ACM/ICPC

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

導航

統計

常用鏈接

留言簿(10)

隨筆分類

隨筆檔案

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            国产精品久久久久7777婷婷| 国产精品爱啪在线线免费观看| 国产目拍亚洲精品99久久精品| 亚洲欧美另类中文字幕| 亚洲午夜视频在线观看| 国产一级精品aaaaa看| 久久久久国产成人精品亚洲午夜| 久久成人免费电影| 亚洲精华国产欧美| 国产精品99久久久久久久久久久久| 国产精品女主播| 美脚丝袜一区二区三区在线观看| 欧美成人小视频| 西瓜成人精品人成网站| 久久久久久久久蜜桃| 一区二区三区四区精品| 欧美一级专区| 日韩一级大片| 久久爱www| 一本一本a久久| 欧美一区在线看| av成人动漫| 久久精品国内一区二区三区| 一本色道**综合亚洲精品蜜桃冫| 亚洲自拍偷拍色片视频| 亚洲激情欧美激情| 香蕉久久夜色| 一本色道综合亚洲| 快she精品国产999| 欧美一区二区高清| 欧美伦理91| 欧美aaaaaaaa牛牛影院| 国产精品亚洲а∨天堂免在线| 欧美激情乱人伦| 国产日韩欧美综合一区| 99视频精品全部免费在线| 在线观看精品一区| 欧美一级欧美一级在线播放| 亚洲无线观看| 欧美成年人网| 免费看亚洲片| 国产中文一区二区| 亚洲一区二区三区三| 妖精视频成人观看www| 美女网站久久| 另类酷文…触手系列精品集v1小说| 国产精品日韩欧美综合| 亚洲精品免费在线播放| 在线观看日韩专区| 久久精品国产99| 久久精品夜色噜噜亚洲aⅴ| 国产精品激情| 夜夜精品视频一区二区| 夜夜狂射影院欧美极品| 欧美成年人视频| 欧美高清视频www夜色资源网| 国产一区二区电影在线观看| 亚洲女人天堂成人av在线| 亚洲一区中文| 国产精品大片| 亚洲小视频在线观看| 亚洲欧美国产精品专区久久| 欧美三区免费完整视频在线观看| 亚洲精品久久久久久久久久久| 亚洲激情专区| 欧美激情一区二区三区在线| 亚洲国产日韩一区二区| 亚洲卡通欧美制服中文| 欧美美女视频| aa日韩免费精品视频一| 亚洲欧美日韩在线| 国产欧美一区二区三区沐欲| 欧美一区=区| 免费看的黄色欧美网站| 亚洲人成在线观看| 欧美人与禽猛交乱配视频| 99视频在线观看一区三区| 亚洲综合视频在线| 国产欧美日韩精品专区| 久久久精品国产一区二区三区| 久久亚洲综合色| 亚洲国产精品尤物yw在线观看 | 久久久久久久网站| 国内精品久久久久久影视8| 久久久五月婷婷| 亚洲国产欧美在线| 亚洲欧美一级二级三级| 国产在线视频欧美一区二区三区| 久久天天躁狠狠躁夜夜爽蜜月| 亚洲国产岛国毛片在线| 亚洲一二三区精品| 国产一区二区三区在线观看网站 | 欧美日韩一区二区视频在线观看| 在线视频欧美一区| 久久嫩草精品久久久精品一| 最新国产精品拍自在线播放| 国产精品video| 久久综合一区| 中文国产成人精品久久一| 久久午夜视频| 亚洲一区三区视频在线观看| 一色屋精品视频在线看| 欧美三级小说| 免费观看在线综合| 亚洲欧美日韩综合一区| 亚洲激情成人在线| 久久久久久久久久久一区| 9l国产精品久久久久麻豆| 国产一区二区三区四区hd| 欧美日韩国产麻豆| 久久米奇亚洲| 亚洲欧美另类中文字幕| 亚洲精品日韩欧美| 免费日韩视频| 久久国产精品久久久久久电车| 99v久久综合狠狠综合久久| 黄色亚洲大片免费在线观看| 国产精品ⅴa在线观看h| 欧美成人精品1314www| 久久成人资源| 午夜欧美大尺度福利影院在线看| 亚洲精品日产精品乱码不卡| 欧美大片va欧美在线播放| 欧美尤物一区| 亚洲欧美一区二区三区在线| 在线激情影院一区| 国产一区二区观看| 国产美女精品一区二区三区| 欧美日韩一区二区三区视频| 欧美成人免费网站| 久久婷婷国产综合国色天香| 亚洲欧美春色| 亚洲一区二区精品在线| 日韩一二三区视频| 亚洲看片网站| 亚洲美女视频网| 亚洲乱码国产乱码精品精天堂| 亚洲电影在线| 欧美激情亚洲激情| 免费久久久一本精品久久区| 久久精品99国产精品日本| 久久国产精品久久精品国产| 久久成人免费| 久久久国产精品一区| 久久久91精品| 久久综合综合久久综合| 美玉足脚交一区二区三区图片| 久久只有精品| 蜜桃伊人久久| 亚洲欧洲三级电影| 日韩亚洲不卡在线| 亚洲一区二区在线免费观看视频 | 亚洲一区三区视频在线观看 | 亚洲激情网址| 亚洲免费观看在线观看| 亚洲桃花岛网站| 亚洲欧美中文日韩在线| 久久国产精品高清| 欧美**人妖| 国产精品va| 国产午夜精品全部视频在线播放| 今天的高清视频免费播放成人| 亚洲国产精选| 亚洲视频在线观看一区| 欧美二区乱c少妇| 欧美经典一区二区| 国产精品国产a| 欲香欲色天天天综合和网| 亚洲人妖在线| 香蕉久久a毛片| 鲁大师影院一区二区三区| 亚洲国产婷婷综合在线精品| 亚洲一二三区在线| 久久免费黄色| 欧美私人网站| 一区在线免费| 亚洲校园激情| 欧美国产乱视频| 亚洲视频网在线直播| 久久久一二三| 国产精品一区二区在线观看| 亚洲欧洲精品一区二区三区不卡 | 久久国内精品自在自线400部| 欧美mv日韩mv国产网站app| 国产精品激情电影| 亚洲韩日在线| 久久国产精品久久久久久| 亚洲日本无吗高清不卡| 欧美中文在线免费| 国产精品成人在线观看| 91久久嫩草影院一区二区| 性娇小13――14欧美| 亚洲国产一区二区三区高清| 欧美一区二区三区视频在线| 欧美日韩蜜桃| 亚洲激情av| 蜜桃久久av| 亚洲欧美日韩精品久久久| 欧美日韩一区二区免费视频| 亚洲黄色成人网|