`
暴风雪
  • 浏览: 388776 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
社区版块
存档分类
最新评论

[Tarjan]uva 4846:Mines

阅读更多

大致题意:

    给出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;
}
 
0
0
分享到:
评论

相关推荐

    LCA (最近公共祖先) Tarjan & 倍增

    LCA Tarjan: 实现原理 理解:离线算法,建好树后再查询,一次DFS 吧所有查询解决完。 时间复杂度:O(n+q); n个点 q次询问 补一下:链式向前星,并查集 ,Tarjan 代码 #include #include #include #include #...

    Tarjan算法精讲

    《Tarjan算法精讲》 Tarjan算法是一种用于查找有向图中强连通分量的高效算法,它基于深度优先搜索(DFS)的思想。在有向图中,如果两个顶点之间存在双向的有向路径,即从一个顶点可以到达另一个顶点,同时另一个...

    Tarjan 的强连通分量算法的Python实现

    Tarjan 的算法将一个有向(可能是循环的!)图作为输入,并以拓扑顺序返回其强连通分量作为输出 循环依赖 在各种情况下,依赖关系可能是循环的,并且必须同时执行一组相互依赖的操作。同时执行成本高昂的情况并不...

    Tarjan Paper

    根据提供的文件信息,本文将重点讨论Tarjan算法以及它在2-SAT问题中的应用。Tarjan算法是一种用于解决图论中强连通分量问题的算法,它由Robert E. Tarjan提出。2-SAT问题,也就是二元可满足性问题,是一个典型的NP...

    tarjan算法

    ### Tarjan算法详解 #### 一、背景及定义 在计算机科学领域,特别是图论中,**强连通分量**是一个重要的概念。对于有向图而言,如果两个顶点之间至少存在一条路径,则这两个顶点被认为是**强连通**的。如果一个有...

    tarjan(e):Tarjan 的强连通分量算法-matlab开发

    实现用于查找有向图的强连通分量的 Tarjan 算法。 在强连通分量 (SCC) 中,每个节点到每个其他节点都有一条路径。 SCC 是不相交的。 入度或出度为零或属于无环图的节点自己形成 SCC。 接受邻接矩阵作为输入。 为了...

    Tarjan 算法论文 DEPTH-FIRST SEARCH AND LINEAR GRAPH ALGORITHMS.pdf

    Tarjan算法是图论领域中一个经典的算法,由美国计算机科学家罗伯特·塔扬(Robert Tarjan)提出,主要用于深度优先搜索(DFS)遍历图中的节点,并对图中的强连通分量(Strongly Connected Components,SCCs)或双...

    tarjan求割边

    Tarjan算法求割边 Tarjan算法是图论中的一种常见算法,用于寻找有向图中的割点和割边。割边是指删除该边后,图将被分割成两个或多个连通分量的边。 Tarjan算法可以快速地找到所有的割边。 割边的定义与割点的定义...

    Tarjan 的 LCA 算法

    **Tarjan的LCA算法详解** 最近公共祖先(Lowest Common Ancestor,简称LCA)是图论中的一个重要概念,特别是在树形结构中。在树中,两个节点的最近公共祖先指的是距离根节点最近的那个同时是这两个节点的祖先的节点...

    tarjan:Tarjan-Languer快速算法,用于在流程图中查找支配者

    Tarjan-Languer快速算法,用于在流程图中查找支配者 原料药 var pipeline = require ( 'tarjan' ) . create ( 'dominance' ) ; // Initialize pipeline // ... // ... var tarjan = require ( 'tarjan' ) . create ...

    tarjan:使用Tarjan算法在Go中进行图形循环检测

    Tarjan是使用Tarjan算法的图循环检测功能。 该算法获取输入图并生成一个切片,其中每个项目都是一个高度连接的顶点的切片。 输入图采用地图的形式,其中键是图形顶点,值是一个切片的for的边。 算法说明: : ...

    Tarjan算法

    **Tarjan算法详解** 在图论和计算机科学中,Tarjan算法是由Robert Endre Tarjan设计的一系列高效算法,主要用于解决图的相关问题,包括强连通分量、拓扑排序和最近公共祖先(Lowest Common Ancestor, LCA)等问题。...

    Tarjan算法讲义

    Tarjan 算法是图论中非常实用 / 常用的算法之一,能解决强连通分量,双连通分量,割点和桥,求最近公共祖先(LCA)等问题。 关于 Tarjan 算法,笔者将用一系列文章系统介绍 Tarjan 算法的原理以及其主要解决的问题...

    连通图tarjan算法动画讲解呕心沥血之作

    tarjan算法呕心沥血之作,动画演示,步步清晰可见,详细的描述了tarjan算法的工作过程,比网上的单纯的图片更加容易理解。

    C++Tarjan算法实现.zip

    《C++实现Tarjan算法详解》 Tarjan算法,全称为Robert Tarjan的强连通分量算法,是图论中的一个经典算法,主要用于找出有向图中的强连通分量。在C++编程中,它能有效地处理复杂的图结构问题,尤其是在分析网络流、...

    LCA的tarjan算法

    对于LCA问题,有不少解法,这儿提供了tarjan算法,这是一种离线算法,读入所有输入然后一并处理,并且利用并查集的思想,从根节点开始DFS,对每一个DFS的节点,先把他的父亲节点指向本身,没访问完一个子节点,然后...

    Tarjan.cbp

    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&gt;&gt;n&gt;&gt;m; int x,y; for(int i=0;i;i++){ cin&gt;&gt;x&gt;&gt;y; Map[x][y]=1; ...

    Tarjan算法模板

    C++实现Tarjan算法的一个简单模板,求有向图的强连通分量。时间复杂度为O(N+M)。

    求有向图的强连通分量(scc)Tarjan算法.docx

    "有向图的强连通分量(scc)Tarjan算法" Tarjan算法是基于深度优先搜索的算法,用于求解有向图的强连通分量(scc)。强连通分量是指图中每两个顶点之间至少存在一条路径的子图。Tarjan算法的主要思想是通过深度...

    Tarjan应用LCA

    标题中的“Tarjan应用LCA”指的是在图论和数据结构领域中,使用Tarjan算法来解决最近公共祖先(Least Common Ancestor, LCA)问题。最近公共祖先是指在一棵树中,两个节点的共同祖先中离根节点最远的一个。LCA问题在...

Global site tag (gtag.js) - Google Analytics