二分

POJ1064

二分绳子长度,可以直接用实数二分,但最后结果注意要向下取整,可以用floor*100再/100去实现

 POJ3273

直接二分额度,可以二分答案的同时二分查找

CF549H

二分差值,当利用这个差值来构造的矩阵最大值>=0且最小值<=0时,一定存在着令其等于0的情况

三分

显然这个x不能太大,也不能太小.

然后就粗略的知道了这是个单峰函数.

三分x,利用前缀和算最大和最小区间和.

然后基于abs比较

BZOJ1857

三分套三分

正确性我不会

在AB上三分一个点,然后在CD上三分一个点算最小距离

POJ1486

将字母在矩形范围内的连边后二分图匹配.

每次去删一条边再跑一边判断这条边是不是必选的.

POJ 2724

二分图匹配

连边的两个数相差一个’1’,显然连边不存在奇环

在连边的时候可以通过c=a^b ,判断c==(c&-c),就可以知道是否只相差1个’1’(学姐太巨了)

还有就是match数组初始化要为-1,因为有0这个数(WA了半天不知道为什么)

 

DINIC求最大流模板

POJ2173

网络流模板题,求1到n的最大流

POJ3041

二分图匹配可做题,把每一行每一列进行匹配即可

POJ3057

还是二分图匹配题,但建图可能比较麻烦,我们把每个时刻的门看做一个节点,枚举时间让人去不断的和门进行匹配,直到一个时刻人匹配上的数量等于总人数就是最小人数.

POJ1149

最大流问题,对于每个买猪的人,可以看做是从上一个人手中买的猪。

这样的话建图就是源点向猪圈建边

猪圈向第一个买猪的人建边

然后每个买猪的人向下一个买这个猪圈猪的人建边

最后人向汇点建边

POJ3281

最大流问题

源点向吃的建边

吃的向牛建边

牛向喝的建边

喝的向汇点建边

但是每头牛只能吃一个喝一个

所以把牛拆成两个点,连一条容量为1的边即可

POJ3469

最小割,按照题中条件建图后跑最小割即可