POJ 3164 Command Network

Stella981
• 阅读 494

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;
}
点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Wesley13 Wesley13
3年前
java将前端的json数组字符串转换为列表
记录下在前端通过ajax提交了一个json数组的字符串,在后端如何转换为列表。前端数据转化与请求varcontracts{id:'1',name:'yanggb合同1'},{id:'2',name:'yanggb合同2'},{id:'3',name:'yang
待兔 待兔
11个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
4年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
Android So动态加载 优雅实现与原理分析
背景:漫品Android客户端集成适配转换功能(基于目标识别(So库35M)和人脸识别库(5M)),导致apk体积50M左右,为优化客户端体验,决定实现So文件动态加载.!(https://oscimg.oschina.net/oscnet/00d1ff90e4b34869664fef59e3ec3fdd20b.png)点击上方“蓝字”关注我
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Wesley13 Wesley13
3年前
35岁是技术人的天花板吗?
35岁是技术人的天花板吗?我非常不认同“35岁现象”,人类没有那么脆弱,人类的智力不会说是35岁之后就停止发展,更不是说35岁之后就没有机会了。马云35岁还在教书,任正非35岁还在工厂上班。为什么技术人员到35岁就应该退役了呢?所以35岁根本就不是一个问题,我今年已经37岁了,我发现我才刚刚找到自己的节奏,刚刚上路。
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
1年前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这
美凌格栋栋酱 美凌格栋栋酱
5个月前
Oracle 分组与拼接字符串同时使用
SELECTT.,ROWNUMIDFROM(SELECTT.EMPLID,T.NAME,T.BU,T.REALDEPART,T.FORMATDATE,SUM(T.S0)S0,MAX(UPDATETIME)CREATETIME,LISTAGG(TOCHAR(