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
|