提高图论精选-图上问题
图论是信息学竞赛中一个非常重要的考察点，本题单主要收录了各类 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:理解二分图本质。}}