首页 > hiho_1139_二分+bfs搜索

hiho_1139_二分+bfs搜索

题目

    给定N个点和M条边，从点1出发，到达点T。寻找路径上边的个数小于等于K的路径，求出所有满足条件的路径中最长边长度的最小值。 

题目链接:二分 

    最小化最大值，考虑采用二分搜索。对所有的边长进行排序，二分，对每次选择的边长，判断是否存在一条路径满足路径上所有的边长度均小于等于该边长，且路径中的边的个数小于等于K。 

    在判断路径是否存在的时候，使用BFS搜索，因为BFS用于寻找最短（边的个数最少）路径。

实现

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct Edge{int to;int dist;int next;
};
//边的个数，开始的时候数组开的长度为 100005， hihocoder上提示 TLE，实际应该为 RE！！！
//数组开到 200005，就AC了
Edge gEdges[200005];
int gHead[10005];
bool gVisited[10005];
int gEdgeIndex;
void Init(){gEdgeIndex = 0;memset(gEdges, -1, sizeof(gEdges));memset(gHead, -1, sizeof(gHead));memset(gVisited, false, sizeof(gVisited));
}
void InsertEdge(int u, int v, int d){int e = gEdgeIndex++;gEdges[e].to = v;gEdges[e].dist = d;gEdges[e].next = gHead[u];gHead[u] = e;
}
struct Node{int id;int step;Node(int i = 0, int s = 0) :id(i), step(s){};
};
//BFS 搜索，寻找从点1到达点boss的路径，要求路径上的所有边的长度都小于等于max_d，且路径长度最大为k
//判断能否找到满足要求的路径
bool Arrive2Boss(int boss, int max_d, int k){queue Q;Node node(1, 1);Q.push(node);memset(gVisited, false, sizeof(gVisited));while (!Q.empty()){node = Q.front();Q.pop();if (node.id == boss)return true;if (gVisited[node.id])continue;gVisited[node.id] = true;for (int e = gHead[node.id]; e != -1; e = gEdges[e].next){int v = gEdges[e].to;if (!gVisited[v] && gEdges[e].dist <= max_d && node.step <= k){Q.push(Node(v, node.step + 1));}}}return false;
}
int edges_len[100005];
int main(){int N, M, K, T, u, v, d;Init();scanf("%d %d %d %d", &N, &M, &K, &T);for (int i = 0; i < M; i++){scanf("%d %d %d", &u, &v, &d);InsertEdge(u, v, d);InsertEdge(v, u, d);edges_len[i] = d;}//对路径进行排序sort(edges_len, edges_len + M);int beg = 0, end = M;//二分查找while (beg < end){int mid = (beg + end) / 2;int max_d = edges_len[mid];if (Arrive2Boss(T, max_d, K)){end = mid;}elsebeg = mid + 1;}int result = edges_len[beg];printf("%d
", result);return 0;
}

 

转载于:https://www.cnblogs.com/gtarcoder/p/5689773.html

更多相关：

  • java 读取excel_Java12POI操作Excel

            Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...

  • C++ 生成随机数

    要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...

  • 基于C++的本征图像分解(Intrinsic Image Decomposition)

    利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 剑指offer：面试题39. 数组中出现次数超过一半的数字

    题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...

  • 剑指offer：面试题33. 二叉搜索树的后序遍历序列

    题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：      5     /    2   6   /  1   3示例 1： 输入: [1,6,3,2,5] 输出...

  • python绝对路径的区别_python学习：绝对路径和相对路径

    大牛们应该对路径都很了解了，这篇文章主要给像我这样的入门小白普及常识用的，啊哈下面的路径介绍针对windows，其他平台的暂时不是很了解。在编写的py文件中打开文件的时候经常见到下面其中路径的表达方式：open('aaa.txt')open('/data/bbb.txt')open('D:\user\ccc.txt')这三种表达式...

  • c++ 工作路径介绍及获取

    1）绝对路径：绝对路径是指目录下的绝对位置，直接到达目标位置，通常是从盘符开始的路径。例如：C:windowssystem32cmd.exe  注意： 在不同系统的情况系 windows下是“”，linux和unix下是“/” ，但在win中没有本质区别。linux和unix系统中绝对路径 以“/”为起始 例：/home/us...

  • 修改IDEA运行jsp文件的时候浏览器地址栏的虚拟访问路径网址

        最终运行效果 当然，这个Application context路径可以直接删掉不需要最终访问路径就会变成http://localhost:8080/...

  • vue引入图片路径的三种主要方法

        1、在js代码里面 或者 html里面用"v-bind:"或":属性名"绑定路径的时候使用 require('@/assets/home/imgName.png') 2、在css或者scss或者html里面的src中引入图片使用（注意如果是:src=后面用第1种方式引入路径） ~@/assets/components...

  • 地图收敛心得170405

    寻路算法大总结! 交换机生成树采用的是完全不同的D-V(distance vector)距离矢量算法,并不是很可靠. 并不是任意两点之间的最短路径,因为任意两点之间取最短路径可能有环路:总权更大 交换机STP不一定是最小生成树!!!举例论证 因为它只是所有交换机到根桥最短 贪心算法的味...

  • PCL点云分割（2）

    关于点云的分割算是我想做的机械臂抓取中十分重要的俄一部分，所以首先学习如果使用点云库处理我用kinect获取的点云的数据，本例程也是我自己慢慢修改程序并结合官方API 的解说实现的，其中有很多细节如果直接更改源程序，可能会因为数据类型，或者头文件等各种原因编译不过，会导致我们比较难得找出其中的错误，首先我们看一下我自己设定的一个场景，...

  • PCL点云配准（2）

    /* 使用正态分布变换进行配准的实验 。其中room_scan1.pcd room_scan2.pcd这些点云包含同一房间360不同视角的扫描数据 */ #include #include #include #include

  • PCL点云变换与移除NaN

    #include #include #include #include ...

  • PCL滤波介绍(3)

    #include #include #include #include #include #include...

  • PCL滤波介绍（2）

    #include #include #include #include int main (int argc,...

©2024 11GX.COM