POJ 1637 Sightseeing tour 混合图欧拉回路 网络流

先考虑联通性,不连通则无解。

再给所有双向边钦点一个方向,和单向边一样记录入度出度。

然后我们考虑,对于一个点,把一条双向边的方向改变,入度-出度的奇偶性是不变的,这样子我们看一下,所有点的入度-出度,如果为奇数,则无解。

然后我们对于每个点,如果其出度大于入度,则从s到i连一条流[……]

Read more

bzoj 3158: 千钧一发 最小割

看到这道题 是没什么思路的。查了一句话题解说是最小割。让我想到了魔术球那题。想找二分图的性质,然而失败了。真是可惜。后来查了题解恍然大悟。

两个偶数显然满足gcd>1的条件。

两个奇数 (2a+1)^2 + (2b+1)^2 = 4a^2 + 4a + ab^2 + 4b + 2[……]

Read more

bzoj 3894: 文理分科 最大流

我们先不考虑一个人周围人选什么。建图就非常显然了。s连向所有人,流量为选文的满意度,所有人向t连边,流量为选理的满意度。然后我们考虑一下如果表示说自己和周围一圈四个人选择一样的科目带来的额外满意度呢。我们考虑新建两组点,分别表示一个人和周围四个人选文/理给这个人带来的额外满意度。我们从s连边到一个点[……]

Read more

bzoj 2132: 圈地计划 网络流

一眼就看出了是网络流,感觉xjb搞一搞很可做。然后xjb搞了半天弃疗了。

我们考虑,如果这道题变成相邻的相同有c的收益就简单了。建一个s,连向所有点,流量为a,所有点连向t,流量为b。相邻的点之间连双向流量为c的边,然后就好了。因为当x,y两个点相邻的点属于同侧时,相邻的点的双向流量不用被割。[……]

Read more

bzoj 3504: [Cqoi2014]危桥 最大流

开始一看这题,woc!裸的网络流啊!这可是bzoj啊!竟然还有这么一道不起眼的水题!!!!

后来写着写着就发现是自己too navie 。边是双向边。。。。然后我就开始纠结,这边应该怎么加。。quq!!会不会有部分a1出来的流量流到b2里面了。。quq!!!一脸蒙蔽啊。。。然后果断弃疗,查题解[……]

Read more

bzoj 4873: [Shoi2017]寿司餐厅 网络流 最大闭合子权图

这题考场上看出来是网络流了,也看出来是最大闭合子权图了,然后建图有一些差错,dinic 神TMD细节写错一直死循环……….然后GG。。

建图还是比较显然的。我们考虑对于每一个区间[i,j]连向[i+1,j] 和[i,j – 1]。如果i == j 就连向寿司i。然后每个寿司连向对应[……]

Read more

bzoj 3438: 小M的作物 最大流 isap

这题开始用dinicT的要死要活,,,,感觉一定是自己哪里写错了。后来听Dev-XYS说,他的dinic也T的要死要活。。用isap就过了。。。确实。。。QAQ

 

建图,我们把S向植物连流量ai的边,植物向T连流量为b的边。对于每一个组合,建立左右个点,然后S向组合这个点连c[……]

Read more

bzoj 2561: 最小生成树 最大流

没有意识到双向边×2=四条边。然后数组就开了2倍,然后就GG。

我们考虑kru最小最小生成树算法。

只要小于l的边可以使图联通,那么就没l这条边的事。所以我们尽可能少的删边,来达到u,v分离。

所以得出算法,我们先对于边权小于l的边跑一遍最小割。

对大于I的边跑一遍最小割,然[……]

Read more

bzoj 3993: [SDOI2015]星际战争 最大流

二分一下,然后最大流就好了,注意eps问题,判断非0与各种相等均需要eps。。

建图很简单,一列点代表武器,一列点代表怪兽,能打到的连inf的边,s到武器连二分时间内总输出即可。