Chrety

分类

C++(8) DOS(2) Python(2) 动态规划(12) 图论(8) 字符串(1) 学习笔记(10) 数学(10) 数据结构(14) 未归档(2) 杂(1) 算法(13) 详尽的思路(1) 题解(1)

/ 注册

全部文章（共4篇）

P2711 小行星 (最大流)

题目 P2711 小行星解析这道题挺巧妙的，乍一看是空间上的，无从下手，稍微转换一下就可以了。看到题目，求消除这些行星的最少次数，就是求最小割，也就是求最大流，考虑怎样建图。考虑当我们消去一个面上的所有点时，我们消去这个面后，这个面就不会再被消了，也就是只能被消一次，比如我们消去与...

网络流最大流

2019-04-30

0 491

P2057 [SHOI2007]善意的投票 (最大流)

题目 P2057 [SHOI2007]善意的投票解析网络流的建模都如此巧妙。我们把同意的意见看做源点\(s\)，不同意的意见看做汇点\(t\)。那我们\(s\)连向所有同意的人，\(t\)连向所有反对的人，流量为1，表示了与其原方案直接冲突的代价，好友之间连双向边（双向边使因为可以...

最大流网络流

2019-05-01

0 505

P1361 小M的作物 (最大流)

题目 P1361 小M的作物解析把\(A\)看做源点，把\(B\)看做汇点，先不考虑额外情况显然，这是一种两者选其一的问题，我们选择一部分边割去，使这部分边的贡献最小，就是求最小割，我们求出了收益最小的情况，又因为只有两种情况，我们取了每一种情况收益较小的一种，所以我们要求的就是总流量...

网络流最大流

2019-05-02

0 563

P2472 [SCOI2007]蜥蜴 (最大流)

题目 P2472 [SCOI2007]蜥蜴解析这个题思路比较清晰，本(qi)来(shi)以(jiu)为(shi)无脑建图跑最大流，结果挂了，整了一个小时后重新建图才过的。建立一个超级源点和一个超级汇点，每个石柱都有其固定的通过的次数，也就是说我们要限制其通过次数，怎么限制呢，拆点，把...

最大流网络流

2019-05-02

0 451