p*****2
发帖数: 21240 | 1 我理解起来还挺费劲，可能做graph的题太少了。
n个city由one way road 相连。现在有问题就是有些城市不能连通，所以需要redirect
roads.
输入每条路redirect的cost，算出把所有城市连通所需要最小的cost。
比如
input
3
1 3 1
1 2 1
3 2 1
output
1
input
3
1 3 1
1 2 5
3 2 1
output
2
input
6
1 5 4
5 3 8
2 4 15
1 6 16
2 3 23
4 6 42
output
39
input
4
1 2 9
2 3 8
3 4 7
4 1 5
output
0 |
r*******n
发帖数: 266 | 2 抢个100084
redirect
【在 p*****2 的大作中提到】
: 我理解起来还挺费劲，可能做graph的题太少了。
: n个city由one way road 相连。现在有问题就是有些城市不能连通，所以需要redirect
: roads.
: 输入每条路redirect的cost，算出把所有城市连通所需要最小的cost。
: 比如
: input
: 3
: 1 3 1
: 1 2 1
: 3 2 1
|
r*******n
发帖数: 266 | 3 弄出strongly connected component, 是个dag吧...然后把dag的sink和source连起来,
就是一整个connected component了
redirect
【在 p*****2 的大作中提到】
: 我理解起来还挺费劲，可能做graph的题太少了。
: n个city由one way road 相连。现在有问题就是有些城市不能连通，所以需要redirect
: roads.
: 输入每条路redirect的cost，算出把所有城市连通所需要最小的cost。
: 比如
: input
: 3
: 1 3 1
: 1 2 1
: 3 2 1
|
m****i
发帖数: 650 | |
p*****2
发帖数: 21240 | 5
3
1 3 1
1 2 1
3 2 1
三个城市
城市1－3 one way road, 如果换方向的话cost是1
【在 m****i 的大作中提到】
: 解释一下input
|
