提高图论精选-图上问题
题单介绍
图论是信息学竞赛中一个非常重要的考察点，本题单主要收录了各类 CSP-S 知识点范围和以绿~紫为主难度的图论中图上问题的好题。
$\text{2022.10.25 Update:增加了 P4376。}$
$\text{2022.11.20 Update:删除了模板题。}$
$\text{2023.3.8 Update:应用户}$ @[__include__](/user/537687) $\text{推荐增加了 P8817。}$
$\text{2023.10.23 Update:增加了 P2573。}$
本题单将不断更新。
- $\large\color{black}{\texttt{图上问题}}$
- $\color{black}{\texttt{最短路}}$
- $\color{black}{\texttt{P1073:考虑将一个问题分成两个问题来解决。}}$
- $\color{black}{\texttt{P1119:理解 Floyd 本质。}}$
- $\color{black}{\texttt{P1347:有意思的 Floyd。}}$
- $\color{black}{\texttt{P4308:倍增Floyd。}}$
- $\color{black}{\texttt{P1522:小白逛公园思想+Floyd。}}$
- $\color{black}{\texttt{P1841:记录最短路上关键节点。}}$
- $\color{black}{\texttt{P1875:最短路建边技巧+最短路计数。}}$
- $\color{black}{\texttt{P1462:二分答案最短路。}}$
- $\color{black}{\texttt{P8817:最短路+贪心。}}$
- $\color{black}{\texttt{P2865:次短路模板。}}$
- $\color{black}{\texttt{P4568:分层图模板。}}$
- $\color{black}{\texttt{P1266:类似于的分层图思想。}}$
- $\color{black}{\texttt{拓扑排序}}$
- $\color{black}{\texttt{P2661:拓扑排序求最小环。}}$
- $\color{black}{\texttt{P1038:拓扑排序经典转换。}}$
- $\color{black}{\texttt{CF1100E:二分+拓扑排序。}}$
- $\color{black}{\texttt{P3243:优先队列拓扑排序。}}$
- $\color{black}{\texttt{P1954:优先队列拓扑排序。}}$
- $\color{black}{\texttt{P4376:优先队列拓扑排序+二分答案。}}$
- $\color{black}{\texttt{差分约束}}$
- $\color{black}{\texttt{P1993:边权简单转换。}}$
- $\color{black}{\texttt{P2294:带技巧性的差分约束。}}$
- $\color{black}{\texttt{P7624:带技巧性的差分约束。}}$
- $\color{black}{\texttt{P4926:乘积差分约束。}}$
- $\color{black}{\texttt{生成树}}$
- $\color{black}{\texttt{P2916:带技巧性的最小生成树。}}$
- $\color{black}{\texttt{P1340:在同一图上进行若干次最小生成树的优化方法。}}$
- $\color{black}{\texttt{P1550:最小生成树超级源点思想。}}$
- $\color{black}{\texttt{P2573:有向图最小生成树。}}$
- $\color{black}{\texttt{图的连通性}}$
- $\color{black}{\texttt{有向图问题}}$
- $\color{black}{\texttt{P2341:理解强连通分量本质。}}$
- $\color{black}{\texttt{P3627:缩点应用。}}$
- $\color{black}{\texttt{P2515:缩点应用。}}$
- $\color{black}{\texttt{P2656:缩点应用。}}$
- $\color{black}{\texttt{P2272:缩点应用。}}$
- $\color{black}{\texttt{无向图问题}}$
- $\color{black}{\texttt{P7924:双联通分量缩点应用。}}$
- $\color{black}{\texttt{P2860:缩点应用。}}$
- $\color{black}{\texttt{欧拉路径}}$
- $\color{black}{\texttt{P1341:欧拉路径应用。}}$
- $\color{black}{\texttt{二分图判定}}$
- $\color{black}{\texttt{P1330:理解二分图本质。}}$