MKの图论大礼包

MK收集的图论大礼包，里面包含从基础图论到提高难度的图论题，干货十足。 拓扑排序是较为基础的图论，其思想为在DAG（有向无环图）中每次把所有入度为$0$的点加入队列进行一些操作，一般配合 DP 使用。 - [P4017 最大食物链计数](https://www.luogu.com.cn/problem/P4017) - [P1807 最长路](https://www.luogu.com.cn/problem/P1807) - [P2196 挖地雷](https://www.luogu.com.cn/problem/P2196) - [P2661 信息传递](https://www.luogu.com.cn/problem/P2661) - [P3243 [HNOI2015]菜肴制作](https://www.luogu.com.cn/problem/P3243) 最小生成树是在一个无向连通图中找出一棵边权最小的包含所有$n$个点的算法，求出最小生成树后可以在树上搞很多东西。 - [P3366 【模板】最小生成树](https://www.luogu.com.cn/problem/P3366) - [P2330 [SCOI2005]繁忙的都市](https://www.luogu.com.cn/problem/P2330) - [P2820 局域网](https://www.luogu.com.cn/problem/P2820) - [P1194 买礼物](https://www.luogu.com.cn/problem/P1194) - [P2872 [USACO07DEC]Building Roads S](https://www.luogu.com.cn/problem/P2872) - [P2212 [USACO14MAR]Watering the Fields S](https://www.luogu.com.cn/problem/P2212) 最短路分单源最短路径和全源最短路径，常用的方法有 dijkstra（单源最短路径，不能处理负权边）,SPFA（单源最短路径，可以处理负权边和负环，但速度比 dijkstra 慢）,Floyd（全源最短路径），还有一些不常用的方法（比如 Johnson），对于一些有特殊限制的图，还可以用拓扑排序之类的算法做。最短路还能有许多应用，如求负环。最短路计数就是统计最短路的数量，SPFA 和 dijkstra 都能做，但是和求最短路一样，慎用 SPFA。 - [P3371 【模板】单源最短路径（弱化版）](https://www.luogu.com.cn/problem/P3371) - [P4779 【模板】单源最短路径（标准版）](https://www.luogu.com.cn/problem/P4779) - [P3385 【模板】负环](https://www.luogu.com.cn/problem/P3385) - [P1144 最短路计数](https://www.luogu.com.cn/problem/P1144) - [P1608 路径统计](https://www.luogu.com.cn/problem/P1608) - [P5905 【模板】Johnson 全源最短路](https://www.luogu.com.cn/problem/P5905) - [P1948 [USACO08JAN]Telephone Lines S](https://www.luogu.com.cn/problem/P1948) - [P6190 [NOI Online #1 入门组]魔法](https://www.luogu.com.cn/problem/P6190) - [P1606 [USACO07FEB]Lilypad Pond G](https://www.luogu.com.cn/problem/P1606) - [P4042 [AHOI2014/JSOI2014]骑士游戏](https://www.luogu.com.cn/problem/P4042) 树有许多美妙的性质，许多问题可以在树上解决。以及有一些题目需要在树上维护一些信息，此时可以用树上差分，树剖，dfs 序等解决。 - [SP1437 PT07Z - Longest path in a tree](https://www.luogu.com.cn/problem/SP1437) - [P1395 会议](https://www.luogu.com.cn/problem/P1395) - [P3379 【模板】最近公共祖先（LCA）](https://www.luogu.com.cn/problem/P3379) - [P1352 没有上司的舞会](https://www.luogu.com.cn/problem/P1352) - [P3128 [USACO15DEC]Max Flow P](https://www.luogu.com.cn/problem/P3128) - [P3258 [JLOI2014]松鼠的新家](https://www.luogu.com.cn/problem/P3258) - [P5958 [POI2017]Sabotaż](https://www.luogu.com.cn/problem/P5958) - [P4281 [AHOI2008]紧急集合 / 聚会](https://www.luogu.com.cn/problem/P4281) - [P3384 【模板】轻重链剖分](https://www.luogu.com.cn/problem/P3384) - [P3178 [HAOI2015]树上操作](https://www.luogu.com.cn/problem/P3178) - [P4114 Qtree1（query on tree还有很多，其他的可以自己搜Qtree）](https://www.luogu.com.cn/problem/P4114) - [P1967 货车运输](https://www.luogu.com.cn/problem/P1967) - [P4180 [BJWC2010]严格次小生成树](https://www.luogu.com.cn/problem/P4180) - [CF1108F MST Unification](https://www.luogu.com.cn/problem/CF1108F) - [P1505 [国家集训队]旅游](https://www.luogu.com.cn/problem/P1505) - [P2486 [SDOI2011]染色](https://www.luogu.com.cn/problem/P2486) Tarjan 这个算法可以用来求强联通分量，还可以用来求割点,割边，以及可以用来缩点，缩点后就会变成一个 DAG，在DAG上就可以做拓扑排序之类的。 - [P1656 炸铁路](https://www.luogu.com.cn/problem/P1656) - [P2863 [USACO06JAN]The Cow Prom S](https://www.luogu.com.cn/problem/P2863) - [P3387 【模板】缩点](https://www.luogu.com.cn/problem/P3387) - [P3388 【模板】割点（割顶）](https://www.luogu.com.cn/problem/P3388) - [P2746 [USACO5.3]校园网Network of Schools](https://www.luogu.com.cn/problem/P2746) - [P1407 [国家集训队]稳定婚姻](https://www.luogu.com.cn/problem/P1407) - [P4782 【模板】2-SAT 问题](https://www.luogu.com.cn/problem/P4782) - [P5782 [POI2001] 和平委员会](https://www.luogu.com.cn/problem/P5782) - [P4171 [JSOI2010] 满汉全席](https://www.luogu.com.cn/problem/P4171) 二分图指的是可以把点分成两块，使得每块里的每个点都不能直接相连的图。可以用染色法判断一个图是否为二分图。 - [P1330 封锁阳光大学](https://www.luogu.com.cn/problem/P1330) - [P3386 【模板】二分图最大匹配](https://www.luogu.com.cn/problem/P3386) - [P1525 关押罪犯](https://www.luogu.com.cn/problem/P1525) - [P1640 [SCOI2010]连续攻击游戏](https://www.luogu.com.cn/problem/P1640)