HDU5394 Bomb
题目:http://acm.hdu.edu.cn/showproblem.php?pid=5934
Each bomb has three attributes: exploding radius riri, position (xi,yi)(xi,yi) and lighting-cost cici which means you need to pay cici 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.
InputFirst line contains an integer TT, which indicates the number of test cases.
Every test case begins with an integers NN, which indicates the numbers of bombs.
In the following NN lines, the ith line contains four intergers xixi, yiyi, riri and cici, indicating the coordinate of ith bomb is (xi,yi)(xi,yi), exploding radius is riri and lighting-cost is cici.
Limits
- 1≤T≤201≤T≤20
- 1≤N≤10001≤N≤1000
- −108≤xi,yi,ri≤108−108≤xi,yi,ri≤108
- 1≤ci≤1041≤ci≤104OutputFor every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the minimum cost.Sample Input
1
5
0 0 1 5
1 1 1 6
0 1 1 7
3 0 2 10
5 0 1 4
Sample Output
Case #1: 15
题意:有n个炸弹,每个炸弹放在(x, y)这个位置,它能炸的范围是以 r 为半径的圆,手动引爆这颗炸弹所需代价是c,当一个炸弹爆炸时,
在它爆炸范围内的所有炸弹都将被它引爆,让求把所有的炸弹都引爆,所需的最少代价是多少?
建立单向图,然后缩点,每个点的权值都为它所在联通块的权值的小的那个,然后找到所有入度为0的点,将他们的权值加起来就是结果;
#include<bits/stdc++.h>
using namespace std;
#define met(a, b) memset(a, b, sizeof(a))
typedef long long LL;
const int N=;
const int INF=0x3f3f3f3f;
const double eps=1e-; struct node{
LL x,y,r;
} a[N]; int n,w[N],Min[N],dfn[N],low[N],vis[N];
int Belong[N],Blocks,Stack[N],Top,Time,ind[N];
vector<int> G[N]; void Init()
{
for(int i=; i<=n; i++) G[i].clear();
met(Min, INF); met(ind, );
met(dfn, ); met(low, );
met(Stack, ); met(vis, );
met(Belong, );
Blocks =Top=Time = ;
} void Tajarn(int u)
{
low[u] = dfn[u] = ++Time;
Stack[Top++] = u;
vis[u] = ;
int v;
for(int i=;i<G[u].size();i++)
{
v=G[u][i];
if(!dfn[v])
{
Tajarn(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v]) low[u]=min(low[u],dfn[v]);
} if(low[u]==dfn[u])
{
++Blocks;
do
{
v = Stack[--Top];
Belong[v] = Blocks;
vis[v] = ;
}while(u!=v);
}
} int main()
{
int T, t = ;
scanf("%d", &T);
while(T --)
{
scanf("%d", &n);
Init();
for(int i=;i<=n;i++) scanf("%I64d%I64d%I64d%d",&a[i].x,&a[i].y,&a[i].r,&w[i]);
for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
{
LL d = (a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y);
if(a[i].r*a[i].r>=d) G[i].push_back(j);
}
} for(int i=;i<=n;i++) if(!dfn[i]) Tajarn(i);
for(int i=;i<=n;i++)
{
for(int j=;j<G[i].size();j++)
{
int x = G[i][j];
int u = Belong[i], v = Belong[x];
if(u != v) ind[v] ++;
Min[u] = min(Min[u], w[i]);
Min[v] = min(Min[v], w[x]);
}
} int ans = ;
for(int i=;i<=Blocks;i++) if(ind[i]==) ans+=Min[i]; printf("Case #%d: %d\n", t++, ans);
}
return ;
}
2018-09-10 16:58:27
最新文章
- 图解HTTP
- jQuery 2.0.3 源码分析 事件绑定 - bind/live/delegate/on
- iOS 运行时
- python 类变量和实例变量
- Python 字符串、元组、字典转换成列表
- 使用CSS的类名交集复合选择器
- git config --global core.excludesfile配置gitignore全局文件
- java 图片 批量 压缩 +所有压缩
- JavaScript数据结构与算法(五) 数组基础算法
- HTML 练习拖动面板
- 关于第一次在IDEA上使用lombok时注解完全不起作用
- ubuntu忘记登录密码解决方法
- HTTP 协议详解(转载)
- 终于在nowcoder爆发了的懒惰
- python-day49--前端 html
- OpenACC Hello World
- 系统出现bootmgr is missing解决方式,戴尔dellserver装系统须要特别注意的问题
- Eclipse color theme jsp javascript显示问题
- python 字典格式嵌套,相同项做叠加
- Docker容器技术(目录)