f***n
发帖数: 117 | 1 题目大意就是一个图，每条边有正的权重，同时每条边有一个属性，属于一个集合中的
一个(比如{a,b,c})。
求从一个点到另一个点的路径，要求经过的边满足一些条件，比如至少有一条边的属性
是a有一条是b。
谢谢！ |
p*****2
发帖数: 21240 | 2
DFS吗。
【在 f***n 的大作中提到】
: 题目大意就是一个图，每条边有正的权重，同时每条边有一个属性，属于一个集合中的
: 一个(比如{a,b,c})。
: 求从一个点到另一个点的路径，要求经过的边满足一些条件，比如至少有一条边的属性
: 是a有一条是b。
: 谢谢！
|
h****e
发帖数: 928 | 3 不是BFS吗？一直找到目标点，如果限制条件不满足的话，回溯到
次优点再找。 |
f***n
发帖数: 117 | 4 BFS吧？但是对一个图最简单的bfs方法是什么？
【在 p*****2 的大作中提到】
:
: DFS吗。
|
f***n
发帖数: 117 | 5 我的第一反应也是bfs+dp，但是具体怎么做？怎样对一个图做bfs是最优的？
谢谢。
【在 h****e 的大作中提到】
: 不是BFS吗？一直找到目标点，如果限制条件不满足的话，回溯到
: 次优点再找。
|
p*****2
发帖数: 21240 | 6 图有没有回路？我第一想法就是DFS做brute force。 |
p*****2
发帖数: 21240 | |
p*****2
发帖数: 21240 | 8 不知道Dijstra变形如何，找到了如果不满足条件继续找。 |
f***n
发帖数: 117 | 9 搞定了，用bellman ford的变种，复杂度是O(m*n*s)，m是边数，n是点数，s是集合大
小。
基本上跟带负权重的最短路很类似，除了dp的状态多出一维来保存集合状态。
另外，原来这种问题不是bfs可以搞定的，还是得边数*点数的复杂度一条边一条边的走啊
【在 p*****2 的大作中提到】
: 不知道Dijstra变形如何，找到了如果不满足条件继续找。
|
p*****2
发帖数: 21240 | 10
走啊
你只是做哪里的题呀？bellman ford我还没学过。这算法很有用吗？
【在 f***n 的大作中提到】
: 搞定了，用bellman ford的变种，复杂度是O(m*n*s)，m是边数，n是点数，s是集合大
: 小。
: 基本上跟带负权重的最短路很类似，除了dp的状态多出一维来保存集合状态。
: 另外，原来这种问题不是bfs可以搞定的，还是得边数*点数的复杂度一条边一条边的走啊
|
|
|
w****x
发帖数: 2483 | 11 要我就DFS的brutal force, 每次到达终点后检查是否满足条件再在所有满足条件的结
果中找最优 |
p*****2
发帖数: 21240 | 12
摁。e跟我ie一个l思路
【在 w****x 的大作中提到】
: 要我就DFS的brutal force, 每次到达终点后检查是否满足条件再在所有满足条件的结
: 果中找最优
|
y*******g
发帖数: 6599 | 13 CLRS里面的啊，all pair shortest path 。代码简单。
TC砍图论题目必备
【在 p*****2 的大作中提到】
:
: 摁。e跟我ie一个l思路
|
p*****2
发帖数: 21240 | 14
我就学了Floyd-Warshall和Dijkstra。 还没碰到需要那个的题。有时间得看看。
【在 y*******g 的大作中提到】
: CLRS里面的啊，all pair shortest path 。代码简单。
: TC砍图论题目必备
|
s******t
发帖数: 169 | 15 BF也是单源最短，你说的是floyd吧: )
另外同问楼主做的哪个题目？
poj的一个题目跟您描述的有点像，初始有一个设定——身上有K块钱，过一个点要交一
个点的过路费，问能到终点且路径最短的走法。
http://poj.org/problem?id=1724
【在 y*******g 的大作中提到】
: CLRS里面的啊，all pair shortest path 。代码简单。
: TC砍图论题目必备
|
y*******g
发帖数: 6599 | 16 记混了，，:(
【在 s******t 的大作中提到】
: BF也是单源最短，你说的是floyd吧: )
: 另外同问楼主做的哪个题目？
: poj的一个题目跟您描述的有点像，初始有一个设定——身上有K块钱，过一个点要交一
: 个点的过路费，问能到终点且路径最短的走法。
: http://poj.org/problem?id=1724
|
