- 浏览: 316931 次
- 性别:
- 来自: 珠海
文章分类
最新评论
-
xialluyouyue:
Ubuntu下搭建nodejs+express+mongodb环境简单教程 -
k317544294:
Good 陈迪峰
(开源游戏) DOTA音效版 俄罗斯方块 -
基德KID.1412:
su1216 写道竖线代表或者,不代表替换
对哦~ 谢谢你的提 ...
正则表达式中特殊字符的用法(收藏) -
su1216:
竖线代表或者,不代表替换
正则表达式中特殊字符的用法(收藏) -
qiqijianglu:
基德KID.1412 写道qiqijianglu 写道基德KI ...
【高斯消元 求期望】HDU 4418 Time travel
http://acm.hdu.edu.cn/showproblem.php?pid=1598
题意:找到从起点到终点的一条路,而且这条路经过的边的最大权值与最小权值之差最小,输出这个差
①最短路+二分枚举
二分枚举差,再枚举下界,上界=下界+差,在上下界的限制之下仍可到达终点,说明存在这么一个差,但是差还可能更小,所以继续二分
②并查集+贪心
枚举最小边,再从小到大一直加大于等于这个最小边的其他边,直到起点跟终点属于同一个集合为止,然后用最大边-最小边的差,看能不能更新mins【结果】
题意:找到从起点到终点的一条路,而且这条路经过的边的最大权值与最小权值之差最小,输出这个差
①最短路+二分枚举
二分枚举差,再枚举下界,上界=下界+差,在上下界的限制之下仍可到达终点,说明存在这么一个差,但是差还可能更小,所以继续二分
#include <iostream> #include <algorithm> #include <queue> using namespace std; #define inf 0x3fffffff #define M 205 //最大点数 struct son{ int v, w; }; vector<son> g[M]; bool inq[M]; //入队列标记 int dist[M], tp[1005], n; //n:实际点数 void init () { for (int i = 1; i <= n; i++) g[i].clear(); } bool spfa (int u, int low, int high, int t) { int i, v, w; for (i = 1; i <= n; i++) { dist[i] = inf; inq[i] = false; } queue<int> q; q.push (u); inq[u] = true; dist[u] = 0; while (!q.empty()) { u = q.front(); q.pop(); inq[u] = false; for (i = 0; i < g[u].size(); i++) { v = g[u][i].v; w = g[u][i].w; if (w < low || w > high) //限制条件 continue; if (dist[u] + w < dist[v]) { if (v == t) //可以到达终点返回true return true; dist[v] = dist[u] + w; if (!inq[v]) { q.push (v); inq[v] = true; } } } } return false; } int main() { bool flag; int m, u, v, i, l, r, mid, maxs; son x; while (~scanf ("%d%d", &n, &m)) { init(); maxs = 0; for (i = 0; i < m; i++) { scanf ("%d%d%d", &u, &v, tp+i); if (maxs < tp[i]) maxs = tp[i]; x.v = v, x.w = tp[i]; g[u].push_back (x); x.v = u; g[v].push_back (x); } sort (tp, tp+m); //边的权值从小到大排序 int q; scanf ("%d", &q); while (q--) { scanf ("%d%d", &u, &v); l = 0, r = maxs; int ans = -1; while (l <= r) //二分枚举舒适度差 { flag = false; mid = (l+r) >> 1; //mid就是差 for (i = 0; tp[i] + mid <= maxs; i++) { if (spfa (u, tp[i], tp[i]+mid, v)) { flag = true; break; } } if (flag) ans = mid, r = mid - 1; else l = mid + 1; } printf ("%d\n", ans); } } return 0; }
②并查集+贪心
枚举最小边,再从小到大一直加大于等于这个最小边的其他边,直到起点跟终点属于同一个集合为止,然后用最大边-最小边的差,看能不能更新mins【结果】
#include <iostream> #include <algorithm> using namespace std; #define inf 0x3fffffff #define M 205 struct edge{ int a, b; int w; }e[1005]; int pre[M], n; int find (int a) { while (a != pre[a]) a = pre[a]; return a; } void init () { for (int i = 1; i <= n; i++) pre[i] = i; } bool cmp (edge x, edge y) { return x.w < y.w; } int main() { int m, i, a, b, q, A, B, j, mins; while (~scanf ("%d%d", &n, &m)) { for (i = 0; i < m; i++) scanf ("%d%d%d", &e[i].a, &e[i].b, &e[i].w); sort (e, e+m, cmp); //边集按权值从小到大排序 scanf ("%d", &q); while (q--) { scanf ("%d%d", &a, &b); mins = inf; for (i = 0; i < m; i++) //枚举最小边 { init(); for (j = i; j < m; j++) //寻找最大边 { A = find (e[j].a); B = find (e[j].b); if (A != B) pre[B] = A; if (find(a) == find(b))//并查集把起点和终点连接起来了就更新mins { //因为有序,所以连接ab的边权值最小为e[i].w,最大为e[j].w if (mins > e[j].w - e[i].w) mins = e[j].w - e[i].w; break; } } if (j == m) //j==m 则继续枚举也不可能令find(a) == find(b) break; } if (mins == inf) puts ("-1"); else printf ("%d\n", mins); } } return 0; }
发表评论
-
【生成树计数】HDU 4305 Lightning
2012-08-16 15:45 2688KIDx的解题报告 题 ... -
【小贪心】USACO Barn Repair
2012-01-15 20:24 896KIDx的解题报告 进入USACO要注册才能看题: h ... -
【预处理+卡特兰数+乘法逆元+二分查找】LOJ 1170
2012-01-14 12:57 2285KIDx 的解题报告 题目链接:http://ligh ... -
【二分】LOJ 1048 Conquering Keokradong
2012-01-14 10:27 1642KIDx 的解题报告 题目链接:http://ligh ... -
LOJ 1009 Back to Underworld
2012-01-10 16:50 0KIDx 的解题报告 题目链接:http://ligh ... -
【floyd的灵活运用】LOJ 1174 Commandos
2012-01-10 15:02 1467KIDx的解题报告 题目链接:http://light ... -
【二分】LOJ 1088 Points in Segments
2012-01-10 14:32 1341KIDx 的解题报告 题目链接:http://ligh ... -
【三分】HDU 2241 考研路茫茫——早起看书
2011-12-09 18:16 1427KIDx 的解题报告 题目链接:http://acm.hdu. ... -
【二分】HDU 2141 Can you find it?
2011-12-07 22:19 1674KIDx 的解题报告 题目链接:http://acm.hdu. ... -
【差分约束(spfa版)】总结
2011-10-05 21:02 7103KIDx 的解题报告 先总结下: 第一: 感觉难点在于建 ... -
【完美匹配-KM算法】HDU总结
2011-10-02 14:35 7198KIDx 的解题报告 题目链接:http://acm.hdu. ... -
【记忆化搜索+最短路】HDU 2833 WuKong
2011-08-28 09:49 2539http://acm.hdu.edu.cn/showprobl ... -
【最短路+枚举】HDU 2962 Trucking【2012-1-20更新】
2011-08-28 09:17 1842KIDx 的解题报告 题目链接:http://acm.hd ... -
【枚举+最短路】HDU 2363 Cycling
2011-08-28 09:07 1806http://acm.hdu.edu.cn/showprobl ... -
【最短路/3大模板】总结【2012-1-22新增前插的spfa】
2011-08-28 18:15 2936首先献上模板:【点都是默认为从1到n编号,用dijk和f ... -
【HDU、二分匹配、最大匹配/新增1005+1008代码】总结
2011-08-22 14:19 1557KIDx 的解题报告 给出基本定义: 第一题:hdu ... -
【floyd/要防重边】HDU 2923 Einbahnstrasse
2011-08-16 21:48 2343http://acm.hdu.edu.cn/showprobl ... -
【floyd记录路径】HDU 1385 Minimum Transport Cost
2011-08-16 21:26 1970http://acm.hdu.edu.cn/showprobl ... -
【最短路spfa+记忆化搜索】HDU 1142 A Walk Through the Forest
2011-08-15 15:21 2211http://acm.hdu.edu.cn/showprobl ... -
【floyd神器】HDU 1217 Arbitrage
2011-08-14 22:09 1788http://acm.hdu.edu.cn/showprobl ...
相关推荐
杭电ACM课件2014版之 (HDUACM201403版_06)并查集(最小生成树)
(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树
acm入门之枚举搜索,学校第一次acm培训,包括枚举及其优化,dfs和bfs
3. (HDUACM2010版_06)并查集(最小生成树).ppt:这是一个PPT文件,可能详细介绍了如何使用并查集来求解最小生成树的问题,包括理论知识、算法流程和示例解析。 4. hdoj1829二分图识别的并查集.txt:二分图是图论...
ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...
1. Dijkstra算法:Dijkstra算法是最常用且基础的单源最短路算法,它使用贪心策略,逐步扩展从源节点s出发的最短路径树。算法保证了每次扩展的都是当前未访问节点中距离源节点最近的一个,最终得到s到所有节点的最短...
- **知识点**:最短路+二分匹配问题。 - **解题思路**:构建二分图模型,使用二分法优化最大匹配算法,同时结合最短路算法求解。 33. **Adopt or not (HDU 3517)** - **知识点**:最大独立集问题。 - **解题...
使用并查集+贪心:先将已有边的权值从大到小排序,又n个点只需n-1条边,这时再遍历一遍,将有边的两点合并为一个队伍,当边的数量达到n-1时退出循环,因为此时已达到最小生成树。 边的权值由大到小排序是因为要将大...
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 ...并查集
1. **基础算法**:如排序(冒泡、选择、插入、快速、归并等)、搜索(线性、二分、深度优先、广度优先等)。 2. **高级算法**:包括动态规划(状态转移、记忆化搜索)、贪心策略、回溯法、分支限界法等。 3. **...
8. **并查集**:并查集是一种用于处理集合合并和查询是否属于同一集合的数据结构。在图论中,它可以用来判断两个节点是否连通,常用于求解连通性问题,如判定树是否为森林或求得强连通分量。 9. **母函数**:在数论...
4. **排序与搜索**:快速排序、归并排序、二分查找等经典算法在HDU题目中经常出现。解题报告会深入讲解这些算法的原理和应用场景,并给出高效的实现代码。 5. **字符串处理**:包括KMP算法、Manacher's Algorithm等...
杭电ACM课件2014版之(HDUACM2010版_13)二分匹配及其应用
贪心算法是在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择策略,以便产生全局最优解的算法。例如,题目1009、1045等,贪心算法要求选手能够识别出局部最优解与全局最优解的关系,通过一系列的局部...
HDU二分匹配及其应用,此PPT是刘春英老师版权所有, 特此贡献给广大编程爱好者,特别是对于ACMer
6. **数据结构**:线段树、斐波那契堆、平衡树(AVL、红黑树)、字典树(Trie)、并查集等,这些高级数据结构可以高效地解决区间查询、维护、集合操作等问题。 7. **几何算法**:二维和三维几何问题,如点线面的...