#图论个人总结三-个人总结
数据范围在50左右的图论相关的题很有可能是整数划分相关。即通过整数划分来枚举图的连通块的情况。
-- 引自课件
Floyd必须保证没有边的变动，最短路才正确
一道构造树的题
有一个n 个点的树，其中每条边有一个正整数边权，你并不知道这棵树的样子，只知道每两点间最短路长度，但是这些最短路长度可能是错误的，请你判断是否存在一棵树满足条件；
注意到边权都是正的；于是乎，对于最小的距离，那条边一定存在于树上，同理，我们求出这个图的最小生成树，这是唯一可能的答案，于是dfs判断一下就可以了；（这道题数据十分良心，样例不水）
见到特殊的二分图匹配，尝试挖掘性质，比如树形DP等
追及问题=逃跑者到达某个点的时间早于追捕者到达某个点的时间，取max即为答案
最小割的可行边和必经边
①对于任意一条满流边(u,v)，(u,v)能够出现在某个最小割集中，当且仅当id[u]!=id[v]；
②对于任意一条满流边(u,v)，(u,v)必定出现在最小割集中，当且仅当id[u]==id[s]且id[v]==id[t]。
注意必须是满流边；
二分图匹配的可行边和必须边
先一次网络流，再跑一次tarjan求连通分量。
边(x,y)是可行边，要求(x,y)已是匹配边或(x,y)是非匹配边，但x和y处在同一个连通分量中。
边(x,y)是必须边，要求(x,y)已是匹配边且x和y不在同一个连通分量中。
01分数规划最优比例环（点权、边权）
在最优比例环中，一定是一个简单环，不会重复经过一个节点多次；
mid*边权-点权
图论建模：背包问题
点双的求法！！！
注意弹栈是弹到
void tarjan(int x,int f)
{
dfn[x]=low[x]=++dk;
st[++tp]=x;
for(ri i=head[x]; i; i=nx[i])
if(v[i]!=f)
{
if(!dfn[v[i]])
{
tarjan(v[i],x), low[x]=min(low[v[i]],low[x]);
if(dfn[x]<=low[v[i]])
{
++tot;
int t;
do
{
t=st[tp--];
adde(tot,t), adde(t,tot);
}
while(t!=v[i]);
adde(tot,x), adde(x,tot);
}
}
else low[x]=min(dfn[v[i]],low[x]);
}
}有向图存在欧拉回路条件：每个点入度等于出度！
无向图判断两点之间是否存在经过奇数条边的路径
如何判断奇环边：跑Tarjan缩点双，在每个点双内部跑二分图染色判定有没有奇环，如果有，则点双内的所有边都在奇环上。
不用二分图染色的好方法：
我们可以在 Tarjan 的 dfs 树上黑(0)白(1)相间染色。如果发现有一条返祖边使得其两端点同色，那么就将后代打上标记。
点双有奇环，当且仅当该点双除了深度最小的那个点外，存在点被标记。
代码
Dilworth定理
对于一个DAG，其最长反链（选最多的点，使两两之间没有路径相连）=最小链覆盖（选最少的链，覆盖所有点）
而最小链覆盖可以用最小流来做，不用传递闭包。
删点变为加点，加点变为加边
利用边双的传递性，往往可以动态缩点
竞赛图的好性质
1.有哈密顿路径
2.若选择一个点，可以覆盖它本身和它的出边，那么最后选择的点数一定不超过
无向图奇数度数
给定一棵无向图，选出一些边，使得每个点度数为奇数。找出任意一棵生成树，在树上DP即可（记录每个点已选的度数，决定它的父边是否选）
原因是如果最优解需要选一条非树边，那么我们可以把
带有特殊边的生成树计数
可以修改矩阵树定理的基尔霍夫矩阵，把特殊边的度数设为x。这种题不仅可用于红蓝边的计数，也可以用于“保留k条原树边”的题。
求二分图最小字典序完美匹配，在一般图上只能逐位确定！O(n^3)
Dij的结构体构造函数，如果dis是LL，参数也一定要是LL！
2-SAT比的是SCC编号！
NOI2017 游戏
这道题一定注意，当条件为假时，命题为真。但是当结论为假时，条件一定为假，不要忘记把这条边加上！当条件为假时，命题的条件就固定了。注意细节！
随机树的直径也是期望O(\log n) 的，所以链修改可以暴力做
给出割集求大小
给出一张图，每次给出一个带方向的边割集（从S指向V-S），求出S的点数。
我们求出这张图的生成树，然后类比矿区，根据父子边和子父边加加减减子树和。
互不相同等于匹配
求最大匹配不方便，可以转为最大独立集