大家好,又见面了,我是全栈君。
Earth Hour
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 125536/65536 K (Java/Others)
Total Submission(s): 1516 Accepted Submission(s): 606
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.
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.
Note that if none of the lights is turned off and the three places are still not connected. Just output -1.
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
每一个灯看做一个点,能互相照亮的点连边。从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账号...