ps做简洁大气网站,英国做暧小视频网站,成都软件开发网站建设,2021小说排行榜百度风云榜tarjan 视频讲解 /*** 题目链接#xff1a;https://vjudge.net/problem/HDU-5934* 题意#xff1a;给你n个炸弹#xff0c;引爆每个炸弹会有一定的花费。每个炸弹给出坐标x#xff0c;y#xff0c;半径r#xff0c;引爆花费#xff1b;* 引爆一个炸弹会把范围内的炸…tarjan 视频讲解 /*** 题目链接https://vjudge.net/problem/HDU-5934* 题意给你n个炸弹引爆每个炸弹会有一定的花费。每个炸弹给出坐标xy半径r引爆花费* 引爆一个炸弹会把范围内的炸弹引爆连锁反应。 现在想把所有炸弹引爆的最小花费。* * 解题思路强连通缩点。根据a能够引爆b可以在建一条a到b的单向边。如果是一个强连通这一部分的图* 任意两点都可以相互到达那么就把这个强连通分量变成一个点值最分量的最小值。这样图就变成有向无环图了。* 考虑到每个点的花费都是大于0的所以引爆开始点最划算即为入度为0的点。* * 前置技能 tarjan 缩点。
*/#include bits/stdc.h
using namespace std;const int maxn100010;
const int INF2e91e8;
vectorintE[maxn];
struct Point
{int x,y,r,cost;
}boom[maxn];
bool judge(Point a,Point b)
{if( 1ll*(a.x-b.x)*(a.x-b.x)1ll*(a.y-b.y)*(a.y-b.y)1ll*a.r*a.r ) return true;return false;
}
int dfn[maxn],low[maxn],id,vis[maxn],ans,deg[maxn];
int num[maxn],cnt,cost[maxn];//对点进行重新编号数组num按照联通分量进行编号
stackintS;
void init()
{idcnt0;memset(deg,0,sizeof(deg));memset(num,0,sizeof(num));memset(vis,0,sizeof(vis));memset(dfn,0,sizeof(dfn));
}
void tarjan(int x)
{low[x]dfn[x]id;S.push(x);vis[x]1;for(int i0;i(int)E[x].size();i){int toE[x][i];if(!dfn[to]) {tarjan(to);low[x]min(low[x],low[to]);}else if(vis[to]) low[x]min(low[x],dfn[to]);}if(low[x]dfn[x]){int mincostINF,in0;cnt;while(1){int nowS.top();S.pop();vis[now]0;num[now]cnt;mincostmin(mincost,boom[now].cost);if(nowx) break;}cost[cnt]mincost;}
}
int main()
{int T,cas1;scanf(%d,T);while(T--){int n;scanf(%d,n);init();for(int i1;in;i){E[i].clear();scanf(%d%d%d%d,boom[i].x,boom[i].y,boom[i].r,boom[i].cost);}for(int i1;in;i){for(int j1;jn;j){if(ij) continue;if(judge(boom[i],boom[j])) E[i].push_back(j);}}for(int i1;in;i)if(!dfn[i]) tarjan(i);for(int i1;in;i){for(int j0;j(int)E[i].size();j){int toE[i][j];if(num[i]!num[to]) deg[num[to]];}}ans0;for(int i1;icnt;i) if(deg[i]0) anscost[i];printf(Case #%d: %d\n,cas,ans);}return 0;
} 转载于:https://www.cnblogs.com/coded-ream/p/7615955.html
