图论 基础训练(一)解题报告

图论 基础训练(一)-by xiaonuolen




A:二分查找

二分模板题,就不多说了

B:jump and jump

这题可以用dp推一下或者用bfs去跑,注意步长0的就点就好了

C:八皇后问题

dfs入门题,不多说了

D:畅通工程

并查集入门题,把每一个城市当作点,然后输入的时候连通两个点,如果已经连了那就不必再连,最后剩下k个点,那么如果全部连起来只要k-1条边就好了

E:城市路

最短路径模板题

F:确定比赛名次

拓扑排序,有bfs和dfs写法,讲下bfs写法。

假设a要在b之前,那么把b点的入度+1,同时把b放到a维护的集合中

for(int i = 0;i<m;i++){

               int a = in.nextInt();

               int b = in.nextInt();

               ru[b]++;

               edge.get(a).add(b);

  }

那么我们先去找入度0的点(也就是没有要求的点,先把放到队列中),然后通过BFS去跑下就好了,因为要求字典序从小到大,所以用下优先队列去存。

下面的是部分关键代码:

 while(!queue.isEmpty()){

     Integer first = queue.poll();

     System.out.print(first);

     List<Integer> list = edge.get(first);//拿到要在该点之后输出的集合

     for(int i = 0;i<list.size();i++){

          ru[list.get(i)]--;//把点的入度减去1

          if(ru[list.get(i)]==0){//如果入度为0了 说明就是没有条件限制了,那么就是可以加入到队列中去了

              queue.add(list.get(i));

          }

     }

}

G:营救天使

BFS简单搜索题,注意下杀死守卫会导致步数多增加了,所以用下优先队列去维护下。

H:学长的象棋加强版

BFS简单搜索题,注意好x和y即可。

I:欧拉回路

并查集题,注意下什么叫欧拉回路。

1.利用并查集来判断是否是连通图

2.一个无向图存在欧拉回路,当且仅当该图所有顶点度数都为偶数,且该图是连通图。

J:Arctic Network

最小生成树的板子题,没什么坑点,注意下点的个数即可

K:流感传染

bfs板子题,不多说了

L:过山车

二分图的板子题

M:Fire Net

dfs搜索题,和八皇后差不多。

N:Number Move

并查集题找环,一开始的时候模拟A的,后面发现并查集就好了,重新去做了一遍,注意好统一的方向,不用去维护父节点更新的问题,只要判断他们两个同一个父节点,就去递归找自己,肯定能找到,统计下中间的个数即可,做个优化判断已经是处于环中,那么下次再来直接不找了,因为肯定是找不到自己了,找几个案例画一下就知道了。就这么混A了

O:图着色问题

图的练习题,没什么太大坑点,判断连通边即可





为解题报告打分
暂时不评分

★★
★★★
★★★★
★★★★★
发表您的评论(若贴AC代码或发表禁止言论等违禁行为将被删除并扣除积分)

|返回 |   | 转到页头|
Copyright @ 2008-2024 (浙ICP备2022001332号), TZOJ. All Rights Reserved.
2017-2024 台州市非普软件技术有限公司,浙江省台州市君悦大厦B幢1603室