Bomb
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 26 Accepted Submission(s): 10
Each bomb has three attributes: exploding radius ri, position (xi,yi) and lighting-cost ci which means you need to pay ci cost making it explode.
If
a un-lighting bomb is in or on the border the exploding area of another
exploding one, the un-lighting bomb also will explode.
Now you know the attributes of all bombs, please use the minimum cost to explode all bombs.
Every test case begins with an integers N, which indicates the numbers of bombs.
In the following N lines, the ith line contains four intergers xi, yi, ri and ci, indicating the coordinate of ith bomb is (xi,yi), exploding radius is ri and lighting-cost is ci.
Limits
- 1≤T≤20
- 1≤N≤1000
- −108≤xi,yi,ri≤108
- 1≤ci≤104
5
0 0 1 5
1 1 1 6
0 1 1 7
3 0 2 10
5 0 1 4
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#define inf 0x3f3f3f3f
#define met(a,b) memset(a,b,sizeof a)
typedef long long ll;
using namespace std;
const int N = 1005;
const int M = 24005;
int vis[N],dfn[N],low[N],head[N],stack1[N],num[N],in[N];
ll cost[N];
int n,m,tot,son,maxn,tim,top,cut;
ll ans;
struct EDG{int to,next;}edg[N*N];
struct node{ll x,y,r,c;}a[N];
bool cmp(node f,node g){return f.c<g.c;}
void add(int u,int v){
edg[tot].to=v;edg[tot].next=head[u];head[u]=tot++;
}
void init(){
met(head,-1);
tot=tim=top=cut=0;
met(vis,0);
met(edg,0);
met(in,0);
met(cost,inf);
met(stack1,0);met(num,0);met(dfn,0);met(low,0);
}
void Tarjan(int u) {
int v;
low[u] = dfn[u] = ++tim;
stack1[top++] = u;
vis[u] = 1;
for(int e = head[u]; e != -1; e = edg[e].next){
v = edg[e].to;
if(!dfn[v]){
Tarjan(v);
low[u] = min(low[u], low[v]);
}else if(vis[v]){
low[u] = min(low[u], dfn[v]);
}
}
if(low[u] == dfn[u]){
cut++;
do{
v = stack1[--top];
num[v] = cut;
cost[cut]=min(cost[cut],a[v].c);
vis[v] = 0;
}while(u != v);
}
}
int main() {
int T;
scanf("%d",&T);
for(int t=1;t<=T;t++){
init();
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld%lld%lld",&a[i].x,&a[i].y,&a[i].r,&a[i].c);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)continue;
if((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)<=a[i].r*a[i].r){
add(i,j);
}
}
}
for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i);
for(int i=1; i<=n; i++) {
for(int j=head[i]; j!=-1; j=edg[j].next) {
int v=edg[j].to;
if(num[i]!=num[v])in[num[v]]++;
}
}
ans=0;
for(int i=1;i<=cut;i++){
if(!in[i])ans+=cost[i];
}
printf("Case #%d: %lld\n",t,ans);
}
return 0;
}