POJ 3164 Command Network

Stella981
• 阅读 359

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
朱刘算法模板

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#define maxn 102
#define maxm 10002
#define inf INT_MAX
 
struct Node{
    double x, y;
} ver[maxn];
struct Node2{
    int u, v;
    double cost;
} edge[maxm];
double ans;
int pre[maxn], hash[maxn], vis[maxn];
double in[maxn];
 
bool ZL_MST(int root, int nv, int ne)
{
    ans = 0;
    int i, u, v, cntnode;
    while(true){
        for(i = 0; i < nv; ++i) in[i] = inf;
        for(i = 0; i < ne; ++i){
            u = edge[i].u; v = edge[i].v;
            if(edge[i].cost < in[v] && u != v){
                pre[v] = u; in[v] = edge[i].cost;
            }
        }
        for(i = 0; i < nv; ++i)
            if(i != root && in[i] == inf) return false;
        memset(hash, -1, sizeof(hash));
        memset(vis, -1, sizeof(vis));
        in[root] = cntnode = 0;
        for(i = 0; i < nv; ++i){
            ans += in[i];
            v = i;
            while(vis[v] != i && hash[v] == -1 && v != root){
                vis[v] = i; v = pre[v];
            }
            if(v != root && hash[v] == -1){
                for(u = pre[v]; u != v; u = pre[u]){
                    hash[u] = cntnode;
                }
                hash[v] = cntnode++;
            }
        }
        if(cntnode == 0) break;
        for(i = 0; i < nv; ++i)
            if(hash[i] == -1) hash[i] = cntnode++;
 
        for(i = 0; i < ne; ++i){
            v = edge[i].v;
            edge[i].u = hash[edge[i].u];
            edge[i].v = hash[edge[i].v];
            if(edge[i].u != edge[i].v){
                edge[i].cost -= in[v];
            }
        }
 
        nv = cntnode;
        root = hash[root];
    }
    return true;
}
 
int main()
{
    int n, m, a, b, i;
    double x, y;
    while(scanf("%d%d", &n, &m) == 2){
        for(i = 0; i < n; ++i)
            scanf("%lf%lf", &ver[i].x, &ver[i].y);
        for(i = 0; i < m; ++i){
            scanf("%d%d", &a, &b);
            x = ver[--a].x - ver[--b].x;
            y = ver[a].y - ver[b].y;
            edge[i].cost = sqrt(x * x + y * y);
            edge[i].u = a; edge[i].v = b;
        }
        if(ZL_MST(0, n, m)) printf("%.2lf\n", ans);
        else printf("poor snoopy\n");
    }
    return 0;
}
点赞
收藏
评论区
推荐文章
刚刚好 刚刚好
2个月前
css问题
1、 在IOS中图片不显示(给图片加了圆角或者img没有父级) <div<img src""/</div div {width: 20px; height: 20px; borderradius: 20px; overflow: h
晴空闲云 晴空闲云
2个月前
css中box-sizing解放盒子实际宽高计算
我们知道传统的盒子模型,如果增加内边距padding和边框border,那么会撑大整个盒子,造成盒子的宽度不好计算,在实务中特别不方便。boxsizing可以设置盒模型的方式,可以很好的设置固定宽高的盒模型。 盒子宽高计算假如我们设置如下盒子:宽度和高度均为200px,那么这会这个盒子实际的宽高就都是200px。但是当我们设置这个盒子的边框和内间距的时候,那
艾木酱 艾木酱
1个月前
快速入门|使用MemFire Cloud构建React Native应用程序
> MemFire Cloud是一款提供云数据库,用户可以创建云数据库,并对数据库进行管理,还可以对数据库进行备份操作。它还提供后端即服务,用户可以在1分钟内新建一个应用,使用自动生成的API和SDK,访问云数据库、对象存储、用户认证与授权等功能,可专
Wesley13 Wesley13
1年前
Java获得今日零时零分零秒的时间(Date型)
public Date zeroTime() throws ParseException {     Date time = new Date();     SimpleDateFormat simp= new SimpleDateFormat("yyyy-MM-dd 00:00:00");     SimpleDateFormat simp2= new S
Stella981 Stella981
1年前
A Bug's Life POJ
[A Bug's Life](https://www.oschina.net/action/GoToLink?url=https%3A%2F%2Fvjudge.net%2Fproblem%2FPOJ-2492) **Background** Professor Hopper is researching the sexual behavior of
Stella981 Stella981
1年前
Hive SQL50道练习题
建表 create table student(s_id string,s_name string,s_birth string,s_sex string) row format delimited fields terminated by '\t';create table course(c_id string,c_name string,t_i
Wesley13 Wesley13
1年前
java 泛型中遇到的问题
首先说下什么是定义带类型参数的泛型例如:  public static <T, S extends T> void Test<T t,S s> {      Systen.out.println(t.getClass().getName());      Systen.out.println(s.getClass().getName
Wesley13 Wesley13
1年前
Go语言 之结构体比较与赋值
package main import ( "fmt" ) type Student struct { id int name string } func main() { //比较 s1 := S
Stella981 Stella981
1年前
Jenkins实现自动运行jmeter脚本
**下载安装包** \--jenkins的war包 下载地址:http://jenkins-ci.org/ 链接:https://pan.baidu.com/s/1VhwgYWqn3Bex2kCHigW5wA 提取码:1ek2 下载的文件:jenkins.war \--ant 下载地址:http://ant.apache.org/ 下载的文件
helloworld_28799839 helloworld_28799839
2个月前
常用知识整理
# Javascript ## 判断对象是否为空 ```js Object.keys(myObject).length === 0 ``` ## 经常使用的三元运算 > 我们经常遇到处理表格列状态字段如 `status` 的时候可以用到 ``` vue