一些比赛暴露出来的问题。
会的太少、不够系统、遗忘太多。
前来填坑之旅。
某些參考这篇文章：http://www.cnblogs.com/kuangbin/p/3228371.html 以及蓝图论书+训练指南。
连通性问题
1、推断可图性
见自己博客里这篇文章 http://blog.csdn.net/cgf1993/article/details/25817693
2、推断单连通
http://blog.csdn.net/cgf1993/article/details/25817693
3、问填加多少条边能够变为全然连通图(基础)
链接：http://poj.org/problem?id=1236
问1：直接缩点+度数推断
问2：即是一个一图填加多少条边为强连通图(max(出度为0的连通分量,入度为0的连通分量))
4、入出度推断 poj2553 http://poj.org/problem?id=2553
思路：题意比較晦涩？YY一下，注意排序。
网络流问题
1、最大流|最小割
poj2112：最大流+二分(基础题、对自己来说是基础中的经典) http://poj.org/problem?id=2112
poj1966：去掉多少个点使图不连通
poj2391：
二分图|覆盖|匹配
1、poj2422(划分关系明白的构图)
关键在于把有向图拆为二分图的技巧,hungary算法直接应用。
poj3020(划分关系不明白二分图构图)
反证法证二分图、匹配两次。好。
2、匹配题目列表
最短路问题|差分约束
1、经典差分约束。
ZOJ2770：http://vjudge.net/problem/viewProblem.action?id=15465
2-SAT
http://vjudge.net/contest/view.action?cid=46632#overview
链接在此，感觉能够一刷
A:裸题。
试了一下多加入�G[x^1].push_back(y); G[y^1].push_back(x);就不正确了。 细节理解问题，x与y不能共存，那选了x必选y^1; 但选了x^1, y与y^1都是随便可选可不选，
所以自己加入�上那两句是错的。
C:几何二分 + 2-SAT
代码地址：https://code.csdn.net/snippets/357389
技巧：i->j’,j->i’的分析。 二分的技巧 :while(r-l>eps)
数据量不大，就该考虑二分哪。
搜索、DP、LCA等
1、LCA裸题：poj1470、poj1330
2、最大团、最大点独立集裸题(dp或搜索) http://vjudge.net/contest/view.action?cid=47430#overview
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/119164.html原文链接：https://javaforall.net
