hdu 3832 Earth Hour (最短路变形)

hdu 3832 Earth Hour (最短路变形)

大家好,又见面了,我是全栈君。

Earth Hour

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 125536/65536 K (Java/Others)
Total Submission(s): 1516    Accepted Submission(s): 606




Problem Description
Earth Hour is an annual international event created by the WWF (World Wide Fund for Nature/World Wildlife Fund), held on the last Saturday of March, that asks households and businesses to turn off their non-essential lights and electrical appliances for one hour to raise awareness towards the need to take action on climate change. 

To respond to the event of this year, the manager of Hunan University campus decides to turn off some street lights at night. Each street light can be viewed as a point in a plane, which casts flash in a circular area with certain radius.

What’s more, if two illuminated circles share one intersection or a point, they can be regarded as connected.

Now the manager wants to turn off as many lights as possible, guaranteeing that the illuminated area of the library, the study room and the dormitory are still connected(directly or indirectly). So, at least the lights in these three places will not be turned off.

 


Input
The first line contains a single integer T, which tells you there are T cases followed.

In each case:

The first line is an integer N( 3<=N<=200 ), means there are N street lights at total.

Then there are N lines: each line contain 3 integers, X,Y,R,( 1<=X,Y,R<=1000 ), means the light in position(X,Y) can illuminate a circle area with the radius of R. Note that the 1st of the N lines is corresponding to the library, the 2nd line is corresponding to the study room, and the 3rd line is corresponding to the dorm.

 


Output
One case per line, output the maximal number of lights that can be turned off.

Note that if none of the lights is turned off and the three places are still not connected. Just output -1.

 


Sample Input
   
   
3 5 1 1 1 1 4 1 4 1 1 2 2 1 3 3 1 7 1 1 1 4 1 1 2 4 1 1 3 1 3 1 1 3 3 1 4 3 1 6 1 1 1 5 1 1 5 5 1 3 1 2 5 3 2 3 3 1

 


Sample Output
   
   
-1 2 1

每一个灯看做一个点,能互相照亮的点连边。从0、1、2三个源点求最短路。然后枚举这3个点到每一个点的最短距离,得到答案。

#include"stdio.h"
#include"string.h"
#include"queue"
#include"vector"
#include"algorithm"
using namespace std;
#define N 205
const int inf=1000000;
int min(int a,int b)
{
    return a<b?a:b;
}
struct node
{
    int x,y,r;
}p[N];
int g[N][N];
int d[3][N];
int judge(int i,int j)   //推断两个灯是否相交
{
    int x,y,d,r;
    x=p[i].x-p[j].x;
    y=p[i].y-p[j].y;
    d=x*x+y*y;
    r=p[i].r+p[j].r;
    if(r*r>=d)
        return 1;
    return 0;
}
void spfa(int s,int n,int *dis)
{
    int i,mark[N];
    memset(mark,0,sizeof(mark));
    for(i=0;i<n;i++)
        dis[i]=inf;
    dis[s]=0;
    queue<int>q;
    q.push(s);
    mark[s]=1;
    while(!q.empty())
    {
        s=q.front();
        q.pop();
        mark[s]=0;
        for(i=0;i<n;i++)
        {
            if(dis[i]>dis[s]+g[s][i])
            {
                dis[i]=dis[s]+g[s][i];
                if(!mark[i])
                {
                    mark[i]=1;
                    q.push(i);
                }
            }
        }
    }
}
int main()
{
    int T,i,j,x,y,r,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d%d%d",&x,&y,&r);
            p[i].x=x;p[i].y=y;p[i].r=r;
        }
        for(i=0;i<n;i++)
        {
            g[i][i]=0;
            for(j=0;j<i;j++)
            {
                if(judge(i,j))
                    g[i][j]=g[j][i]=1;
                else
                    g[i][j]=g[j][i]=inf;
            }
        }
        spfa(0,n,d[0]);
        spfa(1,n,d[1]);
        spfa(2,n,d[2]);
        int ans=inf;
        for(i=0;i<n;i++)
        {
            ans=min(ans,d[0][i]+d[1][i]+d[2][i]);
        }
        if(ans<inf)
            printf("%d\n",n-ans-1);
        else
            printf("-1\n");
    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116368.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 4G与5G网络有哪些区别

    4G与5G网络有哪些区别一、帧结构比较4G和5G相同之处帧和子帧长度均为:10ms和1ms。 最小调度单位资源:RB  4G和5G不同之处1);子载波宽度4G:固定为15kHz。 5G:多种选择,15kHz、30kHz、60kHz、120kHz、240kHz,且一个5G帧中可以同时传输多种子载波带宽。  2);最小调度单位时间4G:TTI,1毫秒; 5G:slot,1/32毫秒~1毫秒,取决于子载波带宽。 此外5G新增mini-slot,最少只占用2个符号。  3);每子帧时

  • DirectSound的应用

    DirectSound的应用

    2021年11月14日
  • C/C++获取当前系统时间的方法

    C/C++获取当前系统时间的方法1、使用系统函数,并且可以修改系统时间#include&lt;stdlib.h&gt;usingnamespacestd;voidmain(){system("time");}备注:获取的为 小时:分钟:秒 信息2、获取系统时间(秒级),可以换算为年月日星期时分秒#include&lt;iostream&gt;#include&lt;time.h&gt;us…

    2022年10月19日
  • pycharm安装anaconda虚拟环境_简单编译器

    pycharm安装anaconda虚拟环境_简单编译器Anaconda虚拟环境和Pycharm选择编译器教程

  • 哈佛幸福课笔记上篇「建议收藏」

    哈佛幸福课笔记上篇「建议收藏」改变一生的课:哈佛幸福课笔记上篇第1课什么是积极心理学?第2课为什么要学习积极心理学?第3课幸福是一种随机现象吗?第4课积极的环境能改变人第5课环境的力量第6课乐观主义第7课逆境还是机遇?第8课感激链接:哈佛大学公开课:幸福课.《哈佛幸福课》是改变我生活最大的一项事物,没有之一。我学习了5遍幸福课,并且用过去6年的时间去尝试它践行它,感觉完全改变了我的生活。第1课什么是积极心理学?1.享受安静2.这门课不光是传授信息,而且关于如何变形。重要的不仅仅是获得了什么信息,还是何形状

  • 头条社招Java岗位-面经

    头条社招Java岗位-面经

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号