大致题意:
给出n个地雷,每颗地雷有一个爆炸范围,这颗地雷爆炸后,这个范围内的地雷都会炸。求最少引爆多少地雷能使得所有的地雷都爆炸。
大致思路:
把每个地雷看作点,每颗地雷都向其能引爆的地雷连边。建图完成后用Tarjan缩点,求出出度为0的强连通分量的个数就是答案。
#include<iostream>
#include<cstdio>
#include <algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int inf=1<<30;
const int nMax=3015;
const int mMax=5001000;
class edge{
public:
int v,nex;
};edge e[mMax];
int k,head[nMax];//head[i]是以点i为起点的链表头部
void addedge(int a,int b){//向图中加边的算法,注意加上的是有向边//b为a的后续节点既是a---->b
e[k].v=b;
e[k].nex=head[a];
head[a]=k;k++;
}
int dfn[nMax],low[nMax],sta[nMax],top,atype,belon[nMax],dep; //atype 强连通分量的个数
bool insta[nMax];
void Tarjan(int u){ //我的Tarjan模版
int i,j;
dfn[u]=low[u]=++dep;
sta[++top]=u;
insta[u]=1;
for(i=head[u];i;i=e[i].nex){
int v=e[i].v;
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else{
if(insta[v])low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
atype++; //强连通分量个数
do{
j=sta[top--];
belon[j]=atype; //第j个点属于第type个连通块
insta[j]=0;
}while(u!=j);
}
}
int out[nMax]; //每个连通块的出度
int in[nMax];
void init(){
k=1;
dep=1;
top=atype=0;
memset(insta,0,sizeof(insta)); //是否在栈中
memset(head,0,sizeof(head)); //静态链表头指针
memset(low,0,sizeof(low)); //Tarjan的low数组
memset(dfn,0,sizeof(dfn)); //Tarjan的dfn数组
memset(out,0,sizeof(out)); //记录每个强连通分量的出度
memset(in,0,sizeof(in)); //记录每个强连通分量的入度
memset(belon,0,sizeof(belon)); //记录每个点属于哪一个强连通分量
}
int mine[nMax][3];
int main(){
int i,j,m,n,a,b,cas,c;
scanf("%d",&cas);
while(cas--)
{
init();
cin>>n;
for(i=0;i<n;i++)
{
cin>>mine[i][0]>>mine[i][1]>>mine[i][2];
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j)continue;
// double len=sqrt((double)mine[i][2]);
int len=mine[i][2]/2;
if(abs(mine[i][0]-mine[j][0])<=len&&abs(mine[i][1]-mine[j][1])<=len)
{
addedge(i,j);
// cout<<i<<" add "<<j<<endl;
}
}
}
for(i=0;i<n;i++)
{
if(!dfn[i])Tarjan(i);
}
for(i=0;i<n;i++)
{
for(j=head[i];j;j=e[j].nex)
{
a=belon[i];
b=belon[e[j].v];
if(a!=b)
{
out[a]++;
in[b]++;
}
}
}
int ans=0;
for(i=1;i<=atype;i++)
{
if(in[i]==0)
{
ans++;
}
}
cout<<ans<<endl;
}
return 0;
}
分享到:
相关推荐
Tarjan 的算法将一个有向(可能是循环的!)图作为输入,并以拓扑顺序返回其强连通分量作为输出 循环依赖 在各种情况下,依赖关系可能是循环的,并且必须同时执行一组相互依赖的操作。同时执行成本高昂的情况并不...
实现用于查找有向图的强连通分量的 Tarjan 算法。 在强连通分量 (SCC) 中,每个节点到每个其他节点都有一条路径。 SCC 是不相交的。 入度或出度为零或属于无环图的节点自己形成 SCC。 接受邻接矩阵作为输入。 为了...
tarjan求割边
Tarjan-Languer快速算法,用于在流程图中查找支配者 原料药 var pipeline = require ( 'tarjan' ) . create ( 'dominance' ) ; // Initialize pipeline // ... // ... var tarjan = require ( 'tarjan' ) . create ...
Tarjan 算法论文 DEPTH-FIRST SEARCH AND LINEAR GRAPH ALGORITHMS.pdf
LCA Tarjan: 实现原理 理解:离线算法,建好树后再查询,一次DFS 吧所有查询解决完。 时间复杂度:O(n+q); n个点 q次询问 补一下:链式向前星,并查集 ,Tarjan 代码 #include #include #include #include #...
Tarjan是使用Tarjan算法的图循环检测功能。 该算法获取输入图并生成一个切片,其中每个项目都是一个高度连接的顶点的切片。 输入图采用地图的形式,其中键是图形顶点,值是一个切片的for的边。 算法说明: : ...
Tarjan算法是用来求有向图的强连通分量的。求有向图的强连通分量的Tarjan算法是以其发明者Robert Tarjan命名的。Robert Tarjan还发明了求双连通分量的Tarjan算法,以及求最近公共祖先的离线Tarjan算法 (本篇文章...
c++写的Tarjan 的 LCA 算法,最近公共祖先算法,可供算法学习参考
最近公共祖先LCA Tarjan算法
更精细的追踪每一个步骤,力求完全剖析算法。
Tarjan 算法是图论中非常实用 / 常用的算法之一,能解决强连通分量,双连通分量,割点和桥,求最近公共祖先(LCA)等问题。 关于 Tarjan 算法,笔者将用一系列文章系统介绍 Tarjan 算法的原理以及其主要解决的问题...
Tarjan应用LCA
对于LCA问题,有不少解法,这儿提供了tarjan算法,这是一种离线算法,读入所有输入然后一并处理,并且利用并查集的思想,从根节点开始DFS,对每一个DFS的节点,先把他的父亲节点指向本身,没访问完一个子节点,然后...
tarjan算法呕心沥血之作,动画演示,步步清晰可见,详细的描述了tarjan算法的工作过程,比网上的单纯的图片更加容易理解。
void Tarjan(int cur); int Map[maxn][maxn]; int n,m; int tol,t; //6 8 //1 3 //1 2 //2 4 //3 4 //3 5 //4 1 //4 6 //5 6 int main() { cin>>n>>m; int x,y; for(int i=0;i;i++){ cin>>x>>y; Map[x][y]=1; ...
Tarjan割点割边,强联通分量讲解
C++实现Tarjan算法的一个简单模板,求有向图的强连通分量。时间复杂度为O(N+M)。
POJ3352-Road Construction 【Tarjan-边双连通分量-缩点】 解题报告+AC代码 http://hi.csdn.net/!s/0T8UO5 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
其中有经典的塔尖(Tarjan)算法: 思路不难理解,因为任何一个强连通分量,必定是对原图的深度优先搜索树的子树。那么其实只要确定每个强连通分量的子树的根,然后根据这些根从树的最低层开始,一个一个的拿出强...