如果不是割点，答案减少2(n-1)
如果删去割点，删去之后整个图分成多个连通块
每一个联通块的大小*其他连通块的大小之和
先求出缩点之后的树
加尽可能少的边使树变成一个边双
找出树上的所有叶子节点（度为一），然后在这些点之间连边直到所有的点度都为一
增广路的匹配边恰好比非匹配边少1
交换两种边，匹配边+1
最大流=最小割
dinic
每一次找到一条路，使得答案可以增加，更改实际流量
对于已经跑满流量的边先忽略他，从s出发bfs，标记每一个点的深度（到s的距离）
如果s到t联通，说明至少有一条增广路。
每次枚举一条出边，强制使用i+1层的边，找到一条路径，将流量更改
退流
加反向边
记录可扩充容量
首先，肯定有一种方案是每一个边对应一个点
不相交也就是说每个点只有一条入边，一条出边
每一种路径覆盖的方案对应了一种二分图匹配。每选中一个点，就有一个点不需要从自己出发
每选择一条出边，也就是在二分图中选择尽可能多的匹配
要最大化二分图选中的边数，因为这样才能减少答案（一个边两个点）
先算出每一个城镇下面能到达的城镇，建二分图，然后跑最小路径覆盖就完了
>和≥的区别
在跑最短路的时候只能跑≥，一般题目都是求整数解
那么我们只需要把边权+1就行了
建图：
x=1 把等号转化成大于等于和小于等于
把严格不等号转移成非严格不等号
每个人的糖果数不小于1
建立一个超级源点，到每一个点连一个长度为1的边。设d[0]=0
最长路算法在求的时候或满足很多限制。如果没有限制是不会凭空增大的
判断正环
为什么不能用最短路？
因为最短路不一定能到达所有的点（边的方向），而此时dis为inf，这显然不是我们想要的
设s[i]为a[i]的前缀和
a[l]+...+a[r]=k----->s[r]-s[l-1]=k
然后差分约束判断有没有解就行了
从任意一个点出发dfs
原文：https://www.cnblogs.com/lcezych/p/11334632.html