Bernard5

题解

作业(2) 学习笔记(17) 技术教程(45) 期末应试(57) 未归档(17) 赛后分析(7) 题集(15)

/ 注册

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

求DAG有向无环图直径 dp 来自专栏

动态规划对状态空间的遍历构成一张有向无环图，遍历顺序就是该有向无环图的一个拓扑序。 #include <bits/stdc++.h> #define sc(x) scanf("%d", &(x)) #define pr(x) printf("%d\n", (x)) #define...

图论 dp

2021-03-28

6 958

矩阵游戏匈牙利算法来自专栏

题意给定一个的01方阵，问是否能够通过行交换和列交换使得主对角线上都是1. 思路主对角线上都是1，这一条件等价于：对于每一行，都有唯一的与之对应的列上是。即可转化为匈牙利算法。 Solution #include <bits/stdc++.h> #define sc(x) scan...

二分图图论

2020-12-03

3 790

Graph Coloring I DFS 来自专栏

本题其实考察了一个基础知识：可以将图的结点用两种颜色染色，满足相邻点不同色的图，称为二分图。而在不满足二分图构成条件的图里，一定可以找到一个简单奇环。在明确这一点的基础上，就可以使用dfs对图结构进行染色。在dfs的过程中，用栈保存点结构的遍历信息，从而检索出现奇数环的情况。 #includ...

DFS 二分图图论

2020-12-01

5 613

我是 A 题来自专栏

从叶子节点开始考虑：对于每一个叶子节点，如果它本身可以被K整除，那么肯定可以直接对它和它父亲做切割。也就是说，在这种情况下，父子相连的边是一定要删掉的。而如果不满足这一条件，这条父子相连的边最后一定会加入答案，由于需要让每一个联通块的点权之和都满足，所以如果叶子，就把叶子的点权加到父节点上即可。 ...

DFS 图论

2020-11-14

3 547

并查集 maki和tree 来自专栏

使用并查集合并白色连通块从每一个黑色节点出发，查询黑色节点的每个分支的白色节点数量，再加上彼此相乘即为结果因为回头走了，每个节点都被算了两遍，所以需要cnt/2 #include <bits/stdc++.h> using namespace std; const int maxn...

图论并查集

2020-09-12

1 748

旋转跳跃 - 并查集

一开始我认为本题是最短路，采用了BFS实现，只能过47%的案例。本题的最简思路是并查集。 class Solution { public: int fa[100010], a[100010]; vector<int> vt[100010]; int fin...

图论并查集

2020-07-16

2 622