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

posts - 7,comments - 3,trackbacks - 0
Command Network
Time Limit: 1000MSMemory Limit: 131072K
Total Submissions: 7267Accepted: 2160

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


裸的最小樹形圖,我就是為了檢驗模板....結果還錯了.....%.2lf在POJ上用G++會莫名的掛掉,所以用C++就行了。
代碼:
#include <cstdio>
#include 
<cstring>
#include 
<cmath>
#include 
<algorithm>
#define MAXN 110
#define INF 1e30
using namespace std;

inline 
double sqr(double x)
{
    
return x * x;
}

struct point
{
    
double _x, _y;
    
double dist_with(const point &rh) const
    {
        
return sqrt(sqr(_x - rh._x) + sqr(_y - rh._y));
    }
} po[MAXN];

double g[MAXN][MAXN];

int pre[MAXN];
bool is_out[MAXN];
int vis[MAXN], vcnt;

double solve(int n, int root)
{
    memset(is_out, 
false, n);
    
double ans = 0;
    
while (1)
    {
        
int i, j, k;
        
for (i = 0; i < n; ++i)
            
if (i != root && !is_out[i])
            {
                pre[i] 
= i;
                
for (j = 0; j < n; ++j)
                    
if (!is_out[j] && g[pre[i]][i] > g[j][i])
                        pre[i] 
= j;
                
if (pre[i] == i) throw false;
            }
        
for (i = 0; i < n; ++i)
            
if (i != root && !is_out[i])
            {
                j 
= i;
                vis[i] 
= ++vcnt;
                
while (vis[pre[j]] != vcnt && pre[j] != root)
                {
                    j 
= pre[j];
                    vis[j] 
= vcnt;
                }
                
if (pre[j] == i)
                    
break;
            }
        
if (i == n)
        {
            
for (j = 0; j < n; ++j)
                
if (j != root && !is_out[j])
                    ans 
+= g[pre[j]][j];
            
break;
        }
        j 
= i;
        
do
        {
            is_out[j] 
= true;
            ans 
+= g[pre[j]][j];
            j 
= pre[j];
        } 
while (j != i);
        
for (int j = 0; j < n; ++j)
            
if (vis[j] == vcnt)
                
for (int k = 0; k < n; ++k)
                    
if (!is_out[k])
                    {
                        
if (g[i][k] > g[j][k])
                            g[i][k] 
= g[j][k];
                        
if (g[k][i] > g[k][j] - g[pre[j]][j] && g[k][j] != INF)
                            g[k][i] 
= g[k][j] - g[pre[j]][j];
                    }
        is_out[i] 
= false;
    }
    
return ans;
}

int main()
{
    
int n, m;
    
while (scanf("%d%d"&n, &m) != EOF)
    {
        
for (int i = 0; i < n; ++i)
            
for (int j = 0; j < n; ++j)
                g[i][j] 
= INF;
        
for (int i = 0; i < n; ++i)
            scanf(
"%lf%lf"&po[i]._x, &po[i]._y);
        
for (int i = 0; i < m; ++i)
        {
            
int a, b;
            scanf(
"%d%d"&a, &b);
            
if (a != b)
                g[a 
- 1][b - 1= po[a - 1].dist_with(po[b - 1]);
        }
        
try
        {
            printf(
"%.2lf\n", solve(n, 0));
        }
        
catch (bool)
        {
            printf(
"poor snoopy\n");
        }
    }
    
return 0;
}
posted on 2011-10-15 22:18 LLawliet 閱讀(173) 評論(0)  編輯 收藏 引用 所屬分類: 圖論
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            猛干欧美女孩| 免费高清在线视频一区·| 亚洲国产精品美女| 玖玖玖国产精品| 91久久精品一区| 日韩一级欧洲| 国产日产高清欧美一区二区三区| 欧美在线观看一区| 老司机67194精品线观看| 亚洲人体一区| 亚洲免费在线看| 在线观看日韩av先锋影音电影院| 欧美不卡福利| 国产精品久久久久永久免费观看| 久久国产福利| 欧美第十八页| 久久国产福利国产秒拍| 玖玖综合伊人| 亚洲欧美在线网| 免费不卡欧美自拍视频| 亚洲欧美日韩天堂一区二区| 久久免费少妇高潮久久精品99| 日韩视频在线免费观看| 午夜欧美大片免费观看| 亚洲麻豆国产自偷在线| 欧美一区二区观看视频| 亚洲免费电影在线观看| 欧美一区在线直播| 中文国产成人精品| 久久亚洲不卡| 欧美尤物一区| 欧美日韩精品免费| 欧美va天堂| 国产亚洲一级高清| 一区二区日韩精品| 亚洲卡通欧美制服中文| 久久久国产视频91| 久久精品视频免费观看| 欧美性大战久久久久| 亚洲国产精品久久久久秋霞影院| 国产综合一区二区| 亚洲欧美伊人| 香蕉久久夜色| 欧美午夜无遮挡| 亚洲日本欧美日韩高观看| 伊人天天综合| 久久精品国亚洲| 久久国产日本精品| 国产精品一区二区欧美| 一区二区三区欧美成人| 一本色道久久综合亚洲精品婷婷| 久久一区二区精品| 猫咪成人在线观看| 伊甸园精品99久久久久久| 欧美一区二区三区视频免费| 性久久久久久久| 国产欧美大片| 香蕉国产精品偷在线观看不卡| 亚洲自拍都市欧美小说| 国产精品久久999| 亚洲淫性视频| 久久黄色网页| 一区二区三区在线免费播放| 久久九九全国免费精品观看| 久久久噜噜噜久久人人看| 韩国自拍一区| 免费观看亚洲视频大全| 亚洲国产成人久久| 一区二区av在线| 欧美性色综合| 亚洲欧美成人一区二区三区| 久久九九国产| 在线播放日韩专区| 欧美激情精品久久久久久免费印度| 欧美黄色大片网站| 一区二区免费在线视频| 国产精品久久久久免费a∨大胸| 亚洲一区二区三区四区中文| 久久激情视频| 亚洲欧洲精品一区二区三区不卡 | 久久国产精品色婷婷| 国产一二三精品| 麻豆精品视频在线观看| 亚洲人在线视频| 午夜伦欧美伦电影理论片| 国产一区二区你懂的| 免费h精品视频在线播放| 一区二区av在线| 久久视频国产精品免费视频在线| 在线免费不卡视频| 欧美日韩在线三区| 欧美在线黄色| 亚洲美女一区| 噜噜噜噜噜久久久久久91| 99re热这里只有精品免费视频| 国产精品久久中文| 久久综合九色综合久99| 在线午夜精品自拍| 免费欧美网站| 午夜国产精品视频| 亚洲黄色视屏| 国产日韩欧美综合一区| 欧美电影免费| 久久精品国产999大香线蕉| 亚洲人成在线观看一区二区| 久久国产精品72免费观看| 亚洲精品国产精品国自产在线 | 欧美激情一区二区三区高清视频| 亚洲校园激情| 亚洲精品欧美专区| 猫咪成人在线观看| 久久国产精品99国产| 一区二区三区四区五区在线| 国内成人精品2018免费看| 国产精品va| 欧美另类视频| 免费欧美日韩国产三级电影| 欧美一区二区免费观在线| 99精品黄色片免费大全| 亚洲福利视频专区| 美国成人直播| 久久精品一区| 性亚洲最疯狂xxxx高清| 亚洲夜间福利| 一级日韩一区在线观看| 亚洲精品视频中文字幕| 亚洲国产va精品久久久不卡综合| 国产欧美日本一区二区三区| 国产精品高清在线观看| 欧美视频官网| 国产精品vvv| 欧美日本一道本在线视频| 欧美激情久久久久| 欧美激情区在线播放| 欧美成人久久| 欧美国产日韩精品| 欧美成人免费观看| 欧美国产日韩一区二区| 免费精品视频| 欧美精彩视频一区二区三区| 欧美激情第二页| 欧美连裤袜在线视频| 欧美激情综合亚洲一二区| 欧美区二区三区| 欧美丝袜一区二区三区| 国产精品成人一区二区三区夜夜夜| 欧美日韩中文| 国产精品欧美在线| 国产日韩欧美亚洲一区| 在线播放日韩专区| 亚洲日本理论电影| 一区二区三区四区国产| 欧美亚洲一区二区在线观看| 午夜精品在线观看| 久久露脸国产精品| 亚洲第一黄色网| 一本色道久久综合亚洲精品婷婷| 亚洲五月六月| 久久久精品动漫| 欧美精选午夜久久久乱码6080| 欧美日韩国产999| 国产女主播视频一区二区| 在线高清一区| 亚洲午夜av| 理论片一区二区在线| 亚洲精品欧美在线| 欧美一站二站| 欧美日韩国产一区二区三区| 国产精品无人区| 亚洲黄色在线| 亚洲女ⅴideoshd黑人| 免费观看30秒视频久久| 夜夜嗨av一区二区三区四季av| 小黄鸭视频精品导航| 欧美国产亚洲视频| 国产日韩精品一区| 99精品热6080yy久久| 久久久久免费| 99人久久精品视频最新地址| 久久久久国产精品麻豆ai换脸| 欧美另类高清视频在线| 在线观看视频一区| 亚洲欧美日本国产专区一区| 欧美激情一区二区三级高清视频| 亚洲综合国产| 欧美日韩精品一区二区在线播放| 狠狠色噜噜狠狠狠狠色吗综合| 亚洲少妇在线| 亚洲成人中文| 91久久夜色精品国产网站| 亚洲综合国产精品| 亚洲激情一区二区| 久久精品一区二区| 国产精品天天看| 亚洲色图自拍| 亚洲日本中文| 欧美va天堂| 最近看过的日韩成人| 久久阴道视频| 欧美一区二区视频在线|