进阶图论算法
Login to join training plan
- 图论复习，分层图
- 负环与差分约束
- 有向图的连通性
- 无向图的连通性
- 二分图匹配
- 二分图的覆盖与独立集
Section 1. 图论复习、负环与差分约束
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P4568 [JLOI2011] 飞行路线 | 58 | 11 | 8 |
| P5960 【模板】差分约束 | 70 | 14 | 7 |
| P89 「一本通 3.4 例 1」Intervals | 42 | 6 | 8 |
| P3275 [SCOI2011] 糖果 | 4 | 1 | 10 |
Section 2. 有向图的连通性
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P2863 [USACO06JAN] The Cow Prom S | 53 | 15 | 6 |
| P3387 【模板】缩点 | 49 | 13 | 7 |
| P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G | 56 | 13 | 7 |
| P2272 [ZJOI2007] 最大半连通子图 | 61 | 8 | 8 |
| P2403 [SDOI2010] 所驼门王的宝藏 | 9 | 2 | 10 |
Section 3. 无向图的连通性
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P1656 炸铁路 | 33 | 13 | 6 |
| P8436 【模板】边双连通分量 | 60 | 14 | 7 |
| P3388 【模板】割点（割顶） | 61 | 14 | 7 |
| P100 「一本通 3.6 例 1」Redundant Paths G | 29 | 6 | 8 |
| P3469 [POI2008] BLO-Blockade | 30 | 6 | 8 |
| P101 「一本通 3.6 例 2」矿场搭建 | 10 | 2 | 10 |
Section 4. 二分图匹配
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P1525 [NOIP2010 提高组] 关押罪犯 | 4 | 4 | 10 |
| P3386 【模板】二分图最大匹配 | 17 | 7 | 8 |
| P10937 車的放置 | 1 | 1 | 10 |
| P10939 骑士放置 | 0 | 0 | (None) |
| P2764 最小路径覆盖问题 | 0 | 0 | (None) |
