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)


相关推荐

  • springboot 之 使用jasypt加密解密插件[通俗易懂]

    springboot 之 使用jasypt加密解密插件[通俗易懂]简单使用jasypt是一个java实现的安全框架1、该工具支持注解方式开启jasypt功能,以及注解方式引入一个或多个需要处理的配置文件。 2、该工具同时支持properties与yml文件的解析处理。 3、该工具支持自定义加解密类型和复写加解密方法。引入插件<dependency> <groupId>com.github.ulisesbocchio&…

  • ORACLE中函数MONTHS_BETWEEN的使用

    ORACLE中函数MONTHS_BETWEEN的使用转自:https://www.cnblogs.com/pumushan/p/6655204.html格式:MONTHS_BETWEEN(DATE1,DATE2)MONTHS_BETWEEN函数返回两个日期之间的月份数。SQL&gt;selectmonths_between(to_date(‘20090228′,’yyyymmdd’),to_date(‘20080228’,’y…

  • 深度搜索算法查找最短路径的方法_深度优先搜索算法

    深度搜索算法查找最短路径的方法_深度优先搜索算法如图,百度地图上有5个地点,各个地点间是单向的路径,试求出从1到5的最短路径。从图中可以得到一个5*5的二维矩阵,利用深度搜索算法,求出最短路径。从最后的运行结果,可以直观的看出搜索的过程代码实现如下:#include"pch.h"#include&lt;stdio.h&gt;#include&lt;stdlib.h&gt;#include&lt;vector&g…

  • python中dropna()什么意思_python dropna函数

    python中dropna()什么意思_python dropna函数我正在尝试平均化熊猫的一组数据。csv文件中的数据。我有一个系列节目叫“轨道”。在前面的阶段中,我使用了dropna()方法来删除在读取csv文件时导入的一些空白行。在我使用的方法是平均5行以上的列。我不能使用滚动平均法,因为我希望使用当前值之前的两行、当前值和当前值之后的两行来获取平均值。在当我得到数据时,我遇到了一些问题,这些数据中的NaN数据已经被删除,因为标签也被删除了。在defget_…

  • try catch的作用

    try catch的作用trycatch的作用:当程序发生错误时,能够保证程序继续执行下去。用一个简单例子说明:1:无trycatchpublicstaticvoidmain(String[]args){ inti; i=2/0; System.out.println(i); System.out.println(1111111111); }运行结果:不会输出1111111112:有tr…

  • Mysql之锁、事务绝版详解—干货!

    Mysql之锁、事务绝版详解—干货!

发表回复

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

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