本月博客排行
-
第1名
wy_19921005 -
第2名
mft8899 -
第3名
java-007 - benladeng5225
- Anmin
年度博客排行
-
第1名
龙儿筝 -
第2名
宏天软件 -
第3名
benladeng5225 - wy_19921005
- vipbooks
- kaizi1992
- 青否云后端云
- e_e
- tanling8334
- sam123456gz
- arpenker
- zysnba
- fantaxy025025
- xiangjie88
- lemonhandsome
- wallimn
- jh108020
- ganxueyun
- Xeden
- xyuma
- zhanjia
- wangchen.ily
- johnsmith9th
- zxq_2017
- forestqqqq
- jbosscn
- daizj
- xpenxpen
- 喧嚣求静
- kingwell.leng
- lchb139128
- kristy_yy
- jveqi
- javashop
- lzyfn123
- sunj
- yeluowuhen
- ajinn
- lerf
- silverend
- chenqisdfx
- xiaoxinye
- flashsing123
- bosschen
- lyndon.lin
- zhangjijun
- sunnylocus
- lyj86
- paulwong
- sgqt
最新文章列表
POJ 3352 Road Construction 无向图割边 + 缩点
来源:http://poj.org/problem?id=3352
题意:在一个岛上有一些旅游景点,旅游景点之间有路。当施工的时候,若一条路在施工,则这条路是不能走得。问至少还需要增加多少条路,能够保证在施工的时候,任意两个旅游景点之间仍然是可通的。
思路:其实就是一个无向图割边 + 缩点的问题。这样考虑,在一个无向图中,如果一条边是割边,则如果这条边在施工,就会产生不可到达的点。因此可以缩 ...
The Busiest Man 强连通分量+缩点+传递闭包 !
/*强连通分量+缩点+传递闭包。有n种物品,现给出m种关系,每种关系a,b对应着物品b能够用物品a来换,然后有q个询问(a,b),问物品a能不能换到物品b。刚开始是判断两个点是否在一个连通分量里,后来想下题目有问单向可达即可,判连通分量范围太小,是错的。这题直接搜索也能过。但是如果qui传递闭包的话,直接用floyed超时。可以先缩点,再对新图求传递闭包。这是一类关系问题中的单向连通。是 ...