Chrety

图论

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

/ 注册

全部文章 / 图论（共8篇）

loj#10078. 新年好(最短路)

题目： loj#10078. 新年好解析：亲戚只有五个，可以把它们看成2,3,4,5,6号点，分别跑最短路，记录一下距离，然后DFS一下这题非常玄学，我开了一个\(12*12\)的数组，没有离散化，竟然过了，开到\(5050*5050\)就RE，玄学代码： #include <...

图论最短路

2019-08-31

0 485

loj#10067 构造完全图(最小生成树)

题目 loj#10067 构造完全图解析和kruscal类似，我们要构造一个完全图，考虑往这颗最小生成树里加边我们先把每一条边存下来，把两个端点分别放在不同的集合内，记录每个集合的大小，然后做kruscal，集合之间两两构造完全图，即两两合并，直到合并成为一个集合。因为本来就有一条边...

图论 kruscal 最小生成树

2019-07-21

0 622

P1347 排序 (拓扑排序,tarjan)

题目 P1347 排序解析打开一看拓扑排序，要判环。三种情况有环（存在矛盾）没环但在拓扑排序时存在有两个及以上的点入度为0（关系无法确定）除了上两种情况（关系可确定）本来懒了一下，直接在排序时判环，然后一直WA，遂怒写tarjan判环，第一个点注意特判两个点...

tarjan 拓扑排序

2019-06-06

0 572

[HNOI2012]矿场搭建 (点双连通)

题目 [HNOI2012]矿场搭建解析这个题做的我十分自闭。。没看出这个是个点双，然后一晚上+半上午。。一看肯定和割点有关，我们找到所有的点双，会发现有这么几种情况连通块中一个割点也没有，这时我们至少要建两个出口，以防万一某个出口塌了就GG了，方案的话就从size（联通块大小...

tarjan 双联通割点

2019-05-25

0 499

P2472 [SCOI2007]蜥蜴 (最大流)

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

最大流网络流

2019-05-02

0 451

P1361 小M的作物 (最大流)

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

网络流最大流

2019-05-02

0 563

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

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

最大流网络流

2019-05-01

0 505

P2711 小行星 (最大流)

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

网络流最大流

2019-04-30

0 491