博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【HDU 5934】Bomb(强连通缩点)
阅读量:5882 次
发布时间:2019-06-19

本文共 3927 字,大约阅读时间需要 13 分钟。

Problem Description

There are N bombs needing exploding.

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.

Input

First line contains an integer T, which indicates the number of test cases.

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

Output

For 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

Source

2016年中国大学生程序设计竞赛(杭州)

题解

把一个炸弹可以炸到另一个看作一条有向边,然后再进行强连通缩点。对于新生成的图,我们只需引燃所有没有边指向的点,即可炸掉所有炸弹。

#include #include 
#include
#include
#include
#include
using namespace std;const int N = 1005; // N为最大点数const int M = 1000005; // M为最大边数struct Edge{ int from, to, nex; bool sign;//是否为桥}edge[M<<1];int head[N], edgenum;void add(int u, int v){//边的起点和终点 Edge E={u, v, head[u], false}; edge[edgenum] = E; head[u] = edgenum++;}int DFN[N], Low[N], Stack[N], top, Time; //Low[u]是点集{u点及以u点为根的子树} 中(所有反向弧)能指向的(离根最近的祖先v) 的DFN[v]值(即v点时间戳)int taj;//连通分支标号,从1开始int Belong[N];//Belong[i] 表示i点属于的连通分支bool Instack[N];vector
bcc[N]; //标号从1开始void tarjan(int u ,int fa){ DFN[u] = Low[u] = ++ Time ; Stack[top ++ ] = u ; Instack[u] = 1 ; for (int i = head[u] ; ~i ; i = edge[i].nex ){ int v = edge[i].to ; if(DFN[v] == -1) { tarjan(v , u) ; Low[u] = min(Low[u] ,Low[v]) ; if(DFN[u] < Low[v]) { edge[i].sign = 1;//为割桥 } } else if(Instack[v]) Low[u] = min(Low[u] ,DFN[v]) ; } if(Low[u] == DFN[u]){ int now; taj ++ ; bcc[taj].clear(); do{ now = Stack[-- top] ; Instack[now] = 0 ; Belong [now] = taj ; bcc[taj].push_back(now); }while(now != u) ; }}void tarjan_init(int all){ memset(DFN, -1, sizeof(DFN)); memset(Instack, 0, sizeof(Instack)); top = Time = taj = 0; for(int i=1;i<=all;i++)if(DFN[i]==-1 )tarjan(i, i); //注意开始点标!!!}vector
G[N];int du[N];void suodian(){ memset(du, 0, sizeof(du)); for(int i = 1; i <= taj; i++)G[i].clear(); for(int i = 0; i < edgenum; i++){ int u = Belong[edge[i].from], v = Belong[edge[i].to]; if(u!=v)G[u].push_back(v), du[v]++; }}int sz;void init(){memset(head, -1, sizeof(head));sz=0; edgenum=0;}int cost[N];map
> vis;int find(int x, int y, int c) { if(!vis[x][y]){vis[x][y]=++sz;cost[sz]=c;} return vis[x][y];}struct node{ int x, y, r, c; node(int tx, int ty, int tr, int tc) { x = tx; y = ty; r = tr; c = tc; } node() {}};node a[N];int ans[N];bool isTouch(int i, int j){ long long dx = a[i].x - a[j].x; long long dy = a[i].y - a[j].y; long long dr = a[i].r; return dx * dx + dy * dy <= dr * dr;}int main(){ int T, ca = 1; cin>>T; int n, x, y, r, c; while (T--) { cin>>n; vis.clear(); init(); for (int i = 0; i < n; i++) { cin>>x>>y>>r>>c; a[i] = node(x, y, r, c); } int id1, id2; for (int i = 0; i < n; i++) { id1 = find(a[i].x, a[i].y, a[i].c); for (int j = 0; j < n; j++) { if (i == j) continue; if (!isTouch(i, j)) continue; id2 = find(a[j].x, a[j].y, a[j].c); add(id1, id2); } } tarjan_init(n); suodian(); int cnt = 0; for (int i = 1; i <= taj; i++) { if (du[i] == 0) { ans[cnt++] = i; } } int sum = 0, tmp = 0; for (int i = 0; i < cnt; i++) { for (int j = 0; j < bcc[ans[i]].size(); j++) { if (j == 0) tmp = cost[bcc[ans[i]][j]]; else tmp = min(tmp, cost[bcc[ans[i]][j]]); } sum += tmp; } cout<<"Case #" << (ca++) << ": " << sum<

转载于:https://www.cnblogs.com/zsyacm666666/p/7250885.html

你可能感兴趣的文章
$digest already in progress 解决办法——续
查看>>
虚拟机 centos设置代理上网
查看>>
Struts2中Date日期转换的问题
查看>>
mysql 数据类型
查看>>
Ubuntu 设置当前用户sudo免密码
查看>>
设置tomcat远程debug
查看>>
android 电池(一):锂电池基本原理篇【转】
查看>>
Total Command 常用快捷键
查看>>
ionic 调用手机的打电话功能
查看>>
怎么使用阿里云直播服务应用到现在主流直播平台中
查看>>
1000 加密算法
查看>>
exif_imagetype() 函数在linux下的php中不存在
查看>>
Ruby的case语句
查看>>
Linux的链接文件-ln命令
查看>>
maven的tomcat插件如何进行debug调试
查看>>
table表头固定
查看>>
截取字符串中两个字符串中的字符串
查看>>
spring xml properties split with comma for list
查看>>
判断点是否在三角形内
查看>>
Android实战简易教程-第二十三枪(基于Baas的用户注冊验证username是否反复功能!)...
查看>>