威风镰鼬

题解

/ 注册

全部文章 / 题解（共13篇）

题解 | #[JSOI2010]连通数#

思路 bitset优化传递闭包模板。代码 #include<bits/stdc++.h> #define inf 0x3f3f3f3f #define int long long using namespace std; const int maxn=2007; bitset<...

字符串 bitset 图论

2021-10-29

1 339

题解 | #可达性#

思路首先tarjan缩点，保证是一个DAG之后，再输出topo排序的起点就可以了。不过数据是不是放水了，我求出来的强连通分量是按访问顺序定谁是fa的，交上去也是对的。难道不应该是要保证每个scc的fa都是里面编号最小那个点吗？所以我弄了个flag数组意义注释了。莫名其妙就A了希望大佬能帮我解答一下...

图论强连通分量

2021-08-31

3 453

题解 | #[ZJOI2007]矩阵游戏#

思路本来想着这是一道最大匹配的水题，没想到忘了变量初始化WA了。用匈牙利算法水过，题意大概是这个意思，假设我们有两个点集X和Y，那么输入就可以转化为二分图两边点的连线情况。交换行列式的过程，实际上是固定一个点集，另外一个点集内部在交换位置（讲得很抽象，画图试试？）然后就可以想到只要每个点都有与之匹...

二分图图论最大匹配

2021-08-25

2 449

题解 | #间谍网络#

思路这道题中，图的遍历起点必然是可控制的，如果起点不可控制，答案肯定是NO,NO的情况只需要从1~n找到第一个没被遍历过的数输出就可以了。因此，我们记录下每个节点的入度，那么就相当于从图中所有入度为0（且可以控制）的点开始拓扑排序，并记录访问节点即可。但是题目不保证是有向无环图，因此我们需要对环进...

tarjan 图论缩点强连通分量

2021-08-13

1 0

题解 | #[SDOI2009]ELAXIA的路线#

思路通过求出dis的交集来得到公共路径。然后重新建一个图。对x1，y1,x2,y2分别进行一次求最短路，交集部分（点的dis相同）进行rebuild，生成一个可拓扑排序求最长路径的DAG.因为做了课件，代码的注释写得很详细，这里就不细讲了。题解 #include <bits/stdc++....

最短路图论拓扑排序

2021-07-28

1 563

题解 | #[HAOI2016]食物链#

思路记忆化搜索、拓扑排序的题目。对于一个已经走过一次的点，后面能走的情况都是确定的，只要能把情况数记录下来，后面的结点就不需要再走一遍了，就可以很大程度上节省时间。代码 #include <bits/stdc++.h> using namespace std; const int...

搜索记忆化图论 dfs 拓扑排序

2021-07-16

1 493

题解 | #[NOIP2015]信息传递#

思路这道题的大意就是要我们求最小环的长度。我们知道这是一个n个顶点n条边的图，所以每一块最多只有一个环，并保证图中有环。我们可以从任意一个点开始搜索，如果碰到了原来记录过的顶点，那么就记录答案并跳出。如果下一个点已经被记录过了并且不是同一次搜索，那么直接跳出就好了。这个是一个O(n)的做法。代码...

dfs 普及组图论环

2021-06-22

1 523

题解 | #没有上司的舞会#

思路树形dp基础题型，dp[i][0]表示i不选中时的最大快乐指数，dp[i][1]表示i选中时的最大快乐指数，所以我们只要先找到一个根节点，然后向下dfs，dp[root][0]和dp[root][1]的较大值就是答案。从下往上状态转移，我们先搜索到叶子节点，然后求出父节点的dp[i][0]和d...

dfs 树普及组图论树形dp

2021-06-16

1 430

题解 | #小G有一个大树#

思路题目都没看懂就莫名其妙A了，“如果结点数相同输出编号小的”，是指平衡点的编号吗？下面题解是按照这样理解的。我先讲一下做题思路吧，数据规模很小，1e3，所以可以把每一个节点当作根去找树的最大深度，最大深度最小的第一个节点可以作为平衡点。找到平衡点之后再来一个push_up对他每一个子节点计算树的...

dfs 树图论

2021-06-16

1 703

题解 | #树上子链#

思路对于一个起始点x，最大子链是从x开始或者从x的子节点开始的最大子链。答案是从x作为起始点得到的最大子链的最大值，起点在dfs过程中走一遍就不会超时了。然后就是树形dp的问题啦。坑点:要开ll，同时注意所有点权值都为负数的情况。代码 #include<bits/stdc++.h> ...

dfs 树图论树形dp

2021-06-16

1 481