首页 > 代码库 > Bomb---hdu5934（连通图 缩点）
Bomb---hdu5934（连通图 缩点）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5934
题意：有n个炸弹，每个炸弹放在(x, y)这个位置，它能炸的范围是以 r 为半径的圆，手动引爆这颗炸弹所需代价是c，当一个炸弹爆炸时，
在它爆炸范围内的所有炸弹都将被它引爆，让求把所有的炸弹都引爆，所需的最少代价是多少？
建立单向图，然后缩点，每个点的权值都为它所在联通块的权值的小的那个，然后找到所有入度为0的点，将他们的权值加起来就是结果；
#include <stdio.h>#include <string.h>#include <algorithm>#include <vector>using namespace std;#define met(a, b) memset(a, b, sizeof(a))typedef long long LL;const int N = 1100;const int INF = 0x3f3f3f3f;const double eps = 1e-10;struct node{ LL x, y, r;}a[N];int n, w[N], Min[N], dfn[N], low[N], vis[N];int Block[N], nBlock, Stack[N], Top, Time, degree[N];vector<int> G[N];void Init(){ for(int i=0; i<=n; i++) G[i].clear(); met(Min, INF);///Min[i]表示缩点之后的每个联通块的最小代价； met(degree, 0);///记录缩点之后的入度； met(dfn, 0); met(low, 0); met(Stack, 0); met(vis, 0); met(Block, 0); nBlock = Top = Time = 0;}void Tajar(int u){ low[u] = dfn[u] = ++Time; Stack[Top++] = u; vis[u] = 1; int v; for(int i=0, len=G[u].size(); i<len; i++) { v = G[u][i]; if(!dfn[v]) { Tajar(v); low[u] = min(low[u], low[v]); } else if(vis[v]) low[u] = min(low[u], dfn[v]); } if(low[u] == dfn[u]) { ++ nBlock; do { v = Stack[--Top]; Block[v] = nBlock; vis[v] = 0; }while(u!=v); }}int main(){ int T, t = 1; scanf("%d", &T); while(T --) { scanf("%d", &n); Init(); for(int i=1; i<=n; i++) scanf("%I64d %I64d %I64d %d", &a[i].x, &a[i].y, &a[i].r, &w[i]); for(int i=1; i<=n; i++)///建图 { for(int j=1; 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=1; i<=n; i++)///缩点； { if(!dfn[i]) Tajar(i); } for(int i=1; i<=n; i++) { for(int j=0,len=G[i].size(); j<len; j++) { int x = G[i][j]; int u = Block[i], v = Block[x]; if(u != v) degree[v] ++; Min[u] = min(Min[u], w[i]); Min[v] = min(Min[v], w[x]); } } int ans = 0; for(int i=1; i<=nBlock; i++) { if(degree[i] == 0) ans += Min[i]; } printf("Case #%d: %d\n", t++, ans); } return 0;}
Bomb---hdu5934（连通图 缩点）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。