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

[dfs+bfs]zoj 3811

 
阅读更多



 题意:

    在一个无向图中,能否按照一定的顺序访问图中的某些点,并且能访问的图中的所有的点

大致解法:

    先dfs一遍这个图是否强连通

    再用bfs判断这个图能否从标记的第1个点走到第k个点

    bfs的时候有一点要注意一下

    我一开始用的是普通的bfs,设一个值vvv,遇到一个标记点则vvv++,用这种办法bfs其实是错的,比如如下样例输出将是no

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int nMax = 100007;
const int mMax = 400008;
int n,m,nk,vis[nMax];
int smark[nMax],sum,marksort[nMax],vvv;
class edge{
public:
    int v,nex;
};edge e[mMax];
int k,head[nMax];
void addedge(int a,int b){
    e[k].v=b;
    e[k].nex=head[a];
    head[a]=k;k++;
}
void dfs(int loc){
    vis[loc]=1;
    sum++;
    for(int i=head[loc];i;i=e[i].nex){
        int v=e[i].v;
        if(!vis[v])dfs(v);
    }
}

bool bfs(){
    queue<int>que;
    int i,cv;
    memset(vis,0,sizeof(vis));
    vis[marksort[0]]=1;
    for(int is=0;is<nk;is++){
        if(vis[marksort[is]]==0)return 0;
        smark[marksort[is]]=0;
        que.push(marksort[is]);
        while(!que.empty()){
            int v=que.front();
            que.pop();
            for(i=head[v];i;i=e[i].nex){
                cv=e[i].v;
                if(!vis[cv]){
                    if(smark[cv]==0){
                        vis[cv]=1;
                        que.push(cv);
                    }else{
                        vis[cv]=1;
                    }
                }
            }
        }
    }
    return 1;
}
int main(){
    int casenum,i,ffa,ffb;
    cin>>casenum;
    while(casenum--){
        cin>>n>>m>>nk;
        memset(smark,0,sizeof(smark));
        for(i=0;i<nk;i++){
            cin>>ffa;
            smark[ffa]=1;
        }
        k=1;
        memset(head,0,sizeof(head));
        for(i=0;i<m;i++){
            cin>>ffa>>ffb;
            addedge(ffa,ffb);
            addedge(ffb,ffa);
        }
        cin>>ffa;
        for(i=0;i<ffa;i++){
            cin>>marksort[i];
        }
        if(ffa<nk){
            cout<<"No\n";
            continue;
        }
        sum=0;
        memset(vis,0,sizeof(vis));
        dfs(1);
        if(sum!=n){
            cout<<"No\n";
            continue;
        }
        if(bfs())cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

 

 

  • 大小: 5.9 KB
0
2
分享到:
评论

相关推荐

    ZOJ月赛 题解 (ZOJ Monthly, August 2014)

    2. **搜索与图论**:深度优先搜索(DFS)、广度优先搜索(BFS)在图论问题中广泛使用,如最短路径、最小生成树、拓扑排序等。理解和熟练运用这些方法能帮助解决复杂的问题。 3. **动态规划(DP)**:动态规划是一种...

    zoj.zip_zoj

    3. **搜索算法**:深度优先搜索(DFS)、广度优先搜索(BFS)、A* 搜索、Dijkstra 算法、Floyd-Warshall 算法等,这些是解决图论问题和路径查找的关键。 4. **动态规划**:背包问题、最长公共子序列、最短路径、...

    zoj代码集合

    5. **图论算法**:包括深度优先搜索(DFS)和广度优先搜索(BFS),以及最小生成树(Prim、Kruskal)和最短路径算法(Bellman-Ford、Dijkstra、SPFA)等。这些都是解决图相关问题的核心技术。 6. **字符串处理**:...

    ZOJ经典源代码(ACM)

    5. **搜索与优化**:深度优先搜索(DFS)和广度优先搜索(BFS)是解决图论问题的常用方法,而A*搜索算法或Dijkstra算法则用于寻找最短路径。在实际编程中,为了提高效率,常常需要进行剪枝和启发式搜索。 6. **记忆...

    ZOJ3180.rar_visual c

    搜索算法如深度优先搜索(DFS)和广度优先搜索(BFS)用于遍历结构。 在Visual C++中实现这些算法时,需要注意内存管理,避免内存泄漏,以及充分考虑程序的时间复杂度和空间复杂度,以满足比赛对于运行时间和内存...

    acm.tar.gz_zoj_zoj题解_题目分类

    5. 深度优先搜索(DFS)和广度优先搜索(BFS):这两种图遍历方法是解决许多搜索问题的基础。 6. 字符串处理:涉及字符串匹配、模式查找、编码解码等问题,经常出现在编程竞赛中。 7. 数据结构:如栈、队列、链表...

    ZOJ解题报告ZOJ解题报告

    解决方案可能涉及深度优先搜索(DFS)或广度优先搜索(BFS),以及动态规划等算法,来模拟网络流量的不同路径和可能性,从而找到最优的流量分配方案。 #### 二、FinancialManagement1048:财务决策模型 ...

    ZOJ四百多道题的源码

    首先,这些源码揭示了不同类型的算法应用,如动态规划、贪心算法、分治法、回溯法、深度优先搜索(DFS)、广度优先搜索(BFS)等。每种算法都有其特定的应用场景和优化技巧,比如动态规划中的记忆化搜索可以减少重复...

    收索资料 特棒的收索资料

    在实际问题中,DFS常被应用于各种题目,例如ZOJ 1711 "Sum It Up",这是一个典型的应用子集树的问题,需要找到满足特定条件的子集。另一个例子是HDOJ 1016 "Prime Ring Problem",虽然题目没有明确指出,但根据问题...

    ACM zoj题目 源代码

    9. **1105FatMouse's Tour.cpp**:题目可能与迷宫求解或最短路径相关,可能要用到深度优先搜索(DFS)或广度优先搜索(BFS)。 10. **1093Monkey and Banana.cpp**:猴子和香蕉的问题可能涉及到动态规划或贪心算法...

    ACM经典常用算法经典常用算法经典常用算法经典常用算法

    #### 广度优先搜索(BFS)和深度优先搜索(DFS) BFS和DFS是两种基本的图遍历算法。BFS从根节点开始,先访问所有距离为1的邻居节点,再访问所有距离为2的节点,以此类推。DFS则从根节点开始,尽可能深地搜索树的分支...

    acm-zju.rar

    2. **搜索算法**:深度优先搜索(DFS)、广度优先搜索(BFS)、二分查找等。 3. **动态规划**:背包问题、最长公共子序列、最短路径问题等。 4. **图论算法**:最小生成树(Prim、Kruskal)、最短路径(Dijkstra、...

    ACMICPC协会程序设计大赛解题报告PPT课件.pptx

    在解决此类问题时,可以使用图的数据结构,如数组或树形结构,以及图的遍历算法,如深度优先搜索(DFS)或广度优先搜索(BFS)来确定连通性。 课件还提到了解题者需要关注的要点,如解题格式、输入输出格式,以及...

    ACM.rar_ACM 绠楁硶_HDU1010_hdu 18

    在原报告中,作者可能没有选择动态规划或贪心策略,而是采用搜索算法,如深度优先搜索(DFS)或广度优先搜索(BFS),甚至可能结合回溯法来寻找解。这种创新性地运用基础算法,可以启示我们如何在实际问题中灵活应用...

    zojacm浙大题目集

    4. **图论**:包括图的遍历(DFS、BFS)、最短路径算法(Dijkstra、Floyd-Warshall)、最小生成树(Prim、Kruskal)等。 5. **字符串处理**:如模式匹配(KMP、Boyer-Moore算法)、文本操作等。 6. **数学问题**:...

    ACMICPC协会程序设计大赛解题报告学习教案.pptx

    可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来确定当前道路网络的连通状态,并计算出最小生成树,如Prim算法或Kruskal算法,以求得最少的新增道路数。 在解题过程中,需要注意输入和输出的格式,确保结果的...

    浙大acm题解

    2. **搜索算法**:包括深度优先搜索(DFS)和广度优先搜索(BFS),常用于解决图和树的遍历问题,以及最短路径问题。 3. **图论算法**:如最短路径算法(Dijkstra、Floyd-Warshall)、最小生成树算法(Prim、...

    ACM大量习题题库及建议培养计划

    - 搜索算法(BFS、DFS)与哈希表应用 - 字符串处理技术(KMP算法等) **第二阶段:深化复杂算法理解** - 进阶图论(如最短路径、网络流) - 动态规划(LCS、背包问题) - 概率统计与组合数学 - A*搜索算法与博弈论...

    ACM计划 训练计划 需要熟练掌握的常规算法

    6. **深度优先搜索与广度优先搜索**:DFS和BFS是图论中最基本的遍历方法,同时掌握哈希表的应用对于提高算法效率至关重要。 7. **数学基础**:如辗转相除法(即欧几里得算法)、线段交点计算及多边形面积计算,这些...

    ACM 竞赛常用算法与数据结构

    - **搜索算法**:深度优先搜索(DFS)、广度优先搜索(BFS)、回溯法等。 - **动态规划**:状态转移方程、记忆化搜索等。 - **图论算法**:最短路径算法(Dijkstra、Floyd-Warshall)、最小生成树(Prim、Kruskal...

Global site tag (gtag.js) - Google Analytics