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

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>
            欧美成人高清视频| 午夜精品久久久久久久蜜桃app | 夜夜爽www精品| 伊人久久av导航| 亚洲视频www| 亚洲美女福利视频网站| 久久在线播放| 久久免费视频网站| 国产视频精品网| 亚洲综合第一页| 亚洲尤物视频网| 欧美日韩一区在线观看视频| 亚洲国产高清一区| 亚洲第一页中文字幕| 久久激情综合| 久久影视精品| 精品96久久久久久中文字幕无| 亚洲欧美视频一区| 欧美有码视频| 国产欧美日韩精品专区| 亚洲主播在线观看| 午夜在线视频观看日韩17c| 欧美日韩在线免费视频| 日韩一区二区精品视频| 一区二区三区高清| 欧美韩国日本综合| 在线精品视频一区二区三四| 久久久久成人网| 另类亚洲自拍| 在线观看91久久久久久| 久久亚洲私人国产精品va媚药| 美女被久久久| 91久久午夜| 欧美激情第4页| 99精品福利视频| 亚洲欧美大片| 国产揄拍国内精品对白| 久久网站热最新地址| 欧美顶级少妇做爰| 一区二区欧美在线| 国产精品自拍在线| 久久久国际精品| 亚洲激情一区二区| 亚洲在线免费| 今天的高清视频免费播放成人| 老鸭窝毛片一区二区三区| 欧美激情女人20p| 亚洲素人一区二区| 国产日韩欧美视频| 欧美成人免费在线观看| 99视频一区| 久久精品一区二区| 亚洲国产三级在线| 国产精品电影观看| 久久精品噜噜噜成人av农村| 亚洲国产精品一区二区第一页 | 影音先锋欧美精品| 欧美福利视频| 亚洲制服av| 免费在线欧美视频| 亚洲天堂成人在线视频| 国产在线不卡精品| 欧美日韩一区二区三区高清| 欧美亚洲在线| 亚洲精品一区二区三区不| 久久精品国产亚洲精品| 亚洲美女中文字幕| 国产一区二区三区观看| 欧美久久一级| 久久se精品一区精品二区| 亚洲精品婷婷| 久久久999精品免费| 亚洲图片在线观看| 亚洲电影下载| 国产日韩亚洲欧美| 欧美日韩国产成人在线观看| 久久av一区二区三区漫画| 亚洲久久一区| 欧美国产精品人人做人人爱| 欧美一区二区三区视频免费| 一区二区三区福利| 亚洲国产成人在线播放| 毛片一区二区| 午夜影院日韩| 亚洲视频精选在线| 亚洲激情小视频| 免费h精品视频在线播放| 欧美在线亚洲| 亚洲男人第一网站| 亚洲素人一区二区| 99精品视频免费观看| 亚洲国产精品久久久久秋霞不卡| 国产欧美日韩另类视频免费观看| 欧美日韩中文字幕在线视频| 欧美成人精品| 女主播福利一区| 久久亚洲综合| 久色婷婷小香蕉久久| 久久精品国产欧美亚洲人人爽| 午夜精品久久久久久久99水蜜桃| 亚洲婷婷在线| 亚洲深爱激情| 亚洲午夜极品| 亚洲影院色在线观看免费| 99国产欧美久久久精品| 亚洲日韩欧美视频| 亚洲免费激情| a4yy欧美一区二区三区| 99精品欧美一区| 一区二区久久久久| 亚洲天堂偷拍| 欧美亚洲网站| 久久精品免费| 免费久久99精品国产自| 欧美国产大片| 欧美日韩免费一区| 国产精品美女久久久久久久| 国产精品久久久久久久久免费樱桃| 国产精品啊啊啊| 国产欧美日韩综合精品二区| 国产亚洲精品一区二555| 伊人春色精品| 亚洲精品欧美日韩| 亚洲一区尤物| 久久久久久亚洲精品中文字幕| 久热精品在线视频| 亚洲国产99精品国自产| 日韩视频专区| 性久久久久久久| 久久午夜精品一区二区| 欧美精品18| 国产精品区一区二区三| 一区二区三区在线高清| 亚洲最新合集| 久久精品国产99精品国产亚洲性色| 久久综合色婷婷| 亚洲精品中文字幕在线观看| 亚洲与欧洲av电影| 免费亚洲电影| 国产欧美精品一区aⅴ影院| 在线观看成人一级片| 亚洲图中文字幕| 久久综合导航| 夜夜嗨网站十八久久| 久久久99免费视频| 欧美无砖砖区免费| 影音先锋中文字幕一区| 亚洲视频在线免费观看| 裸体女人亚洲精品一区| 一道本一区二区| 久久久久一区二区三区| 欧美少妇一区二区| 亚洲国产天堂久久国产91| 羞羞视频在线观看欧美| 亚洲高清中文字幕| 欧美一区二区三区视频在线 | 国产精品久久久久久久久久尿| 黄色成人免费观看| 亚洲网站视频福利| 欧美国产亚洲精品久久久8v| 亚洲欧美日韩国产成人| 欧美经典一区二区| 曰韩精品一区二区| 欧美亚洲三区| 99国产精品99久久久久久| 毛片一区二区三区| 国产综合激情| 欧美亚洲午夜视频在线观看| 亚洲精品免费电影| 美女国内精品自产拍在线播放| 国产欧美亚洲日本| 亚洲一区制服诱惑| 亚洲精品久久久蜜桃| 欧美wwwwww| 欲香欲色天天天综合和网| 欧美在线视频一区二区| 亚洲午夜精品一区二区| 欧美另类在线播放| 亚洲精品婷婷| 欧美好吊妞视频| 久久一区二区三区四区| 国产亚洲精品久久久| 欧美一区二区在线观看| 亚洲视频精选在线| 欧美天堂亚洲电影院在线观看 | 美女尤物久久精品| 尤物yw午夜国产精品视频| 久久精品国产99| 先锋影音国产一区| 国产手机视频精品| 久久久7777| 欧美中文在线字幕| 国产一区91| 久久免费精品日本久久中文字幕| 欧美一区二区三区视频| 激情自拍一区| 欧美黄色日本| 欧美国产日韩精品| 亚洲天天影视| 亚洲一区二区视频|