ComplexPug

分类

做题记录(1) 未归档(274)

/ 注册

全部文章（共5篇）

luogu P3387 【模板】缩点

题目好久没法博客了这次就水个板子题目吧 tarjan缩点之后重新建图而且边权应该都是正的（要不我怎么能这么轻松水过去）在新图上记忆化一下就好了 f[i] 表示开头选i这个点的路径最大值 #include <bits/stdc++.h> using namesp...

tarjan

2018-09-25

1 485

P2860 [USACO06JAN]冗余路径Redundant Paths tarjan

题目链接 https://www.luogu.org/problemnew/show/P2860 思路缩点，之后就成了个树一般的东西了然后（叶子节点+1）/2就是答案，好像贪心的样子，lmc好像讲过诶 cpp #include <iostream> #include <c...

tarjan 树

2019-02-18

0 612

CF1131D tarjan，拓扑

题目链接 541div2 http://codeforces.com/contest/1131/problem/D 思路给出n序列和m序列的相对大小关系构造出最大值最小的序列缩点+拓扑小的向大的连边相等的连个环 tarjan缩点，判断环内是否ok 最后拓扑更新要这样 ans[v]...

CF tarjan 拓扑排序

2019-02-23

0 443

bzoj1565: [NOI2009]植物大战僵尸最大权闭合子图，tarjan

bzoj1565: [NOI2009]植物大战僵尸链接 https://www.lydsy.com/JudgeOnline/problem.php?id=1565 思路很容易的想到最大权闭合子图但这个图是有环的有环的地方当然是都过不去的地方显然他所保护的地方也是过不去的他保护的地...

最大权闭合子图 tarjan 网络流

2019-03-10

0 530

loj#2255. 「SNOI2017」炸弹线段树优化建图，拓扑，缩点

loj#2255. 「SNOI2017」** 线段树优化建图，拓扑，缩点链接 loj 思路用交错关系建出图来，发现可以直接缩点，拓扑统计。完了吗，不，瓶颈在于边数太多了，线段树优化建图。细节建新图要判重。内存永远算不对代码 #include <bits/stdc+...

线段树优化 tarjan 拓扑排序

2019-04-30

0 516