首页 > ACM题库 > HDU-杭电 > HDU 3832-Earth Hour-图-[解题报告]HOJ
2015
04-13

HDU 3832-Earth Hour-图-[解题报告]HOJ

Earth Hour

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

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

样例输出:

-1
2
1

/*
分析:
    竟然用的这个方法过的:
    先算出3个点分别到其它各个点的距离,然后遍历所
有点,求min=MIN(min,dis_1[i]+dis_2[i]+dis_3[i]);
那么结果就是n-d-1。

    实在不明白,为什么这样能ac。比如:这样得出的
点10作为中心是最合适的,那么如果1到10的路径上有边
与2到10的路径上的边重合的话,那么这方法坑定的不对
啊~!

                                                   2012-07-25
*/

#include"stdio.h"
#include"math.h"
#include"string.h"
int queue[5555];


struct A
{
	int x,y;
	int r;
	int total;
	int mem[222];
}E[222];
int n;


int dis[222];
int dis_1[222];
int dis_2[222];
int dis_3[222];


int MIN(int a,int b)
{
	return a>b?b:a;
}


void SPFA(int s)
{
	int key,k;
	int i;
	int hash[222];
	int temp;
	
	for(i=1;i<=n;i++)	dis[i]=1111111;
	dis[s]=0;
	
	memset(hash,0,sizeof(hash));
	k=0;
	key=1;
	queue[0]=s;
	hash[s]=1;
	while(k<key)
	{
		for(i=0;i<E[queue[k]].total;i++)
		{
			temp=dis[queue[k]]+1;
			if(temp<dis[E[queue[k]].mem[i]])
			{
				dis[E[queue[k]].mem[i]]=temp;
				if(!hash[E[queue[k]].mem[i]])
				{
					hash[E[queue[k]].mem[i]]=1;
					queue[key++]=E[queue[k]].mem[i];
				}
			}
		}
		hash[queue[k]]=0;
		k++;
	}
}
int main()
{
	int T;
	int i,l;
	int t1,t2;
	int min;


	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);


		for(i=1;i<=n;i++)	scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].r);
		for(i=1;i<=n;i++)
		{
			E[i].total=0;
			for(l=1;l<=n;l++)
			{
				if(i==l)	continue;
				t1=abs(E[i].x-E[l].x)*abs(E[i].x-E[l].x)+abs(E[i].y-E[l].y)*abs(E[i].y-E[l].y);
				t2=(E[i].r+E[l].r)*(E[i].r+E[l].r);
				if(t2>=t1)	E[i].mem[E[i].total++]=l;
			}
		}


		SPFA(1);
		for(i=1;i<=n;i++)	dis_1[i]=dis[i];
		SPFA(2);
		for(i=1;i<=n;i++)	dis_2[i]=dis[i];
		SPFA(3);
		for(i=1;i<=n;i++)	dis_3[i]=dis[i];


		min=111111;
		for(i=1;i<=n;i++)	min=MIN(min,dis_1[i]+dis_2[i]+dis_3[i]);


		if(min==111111)	printf("-1\n");
		else			printf("%d\n",n-min-1);
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ice_crazy/article/details/7783959


  1. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。