Bernard5

分类

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

/ 注册

TA的专栏 160篇文章 0人订阅

算法竞赛之路

160篇文章 3594人学习

全部文章（共9篇）

几种最短路的简单表述来自专栏

SPFA 思路：初始化dis[]为最大值，dis[x]表示起点到x点的最短路长度建立一个queue，一开始只有起点弹出队头，对于队头节点的每个相邻点，如果能优化当前的路径，就入队，并且优化重复3直到队空 #include <bits/stdc++.h> #define sc(...

最短路图论数据结构

2021-04-23

0 659

求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 955

牛客挑战赛47 来自专栏

https://ac.nowcoder.com/acm/contest/10743 A 思维题。最终的gcd最大值必为排序后每两个相邻数的差值的gcd。那么就计算最小的数需要加多少才能成为这个gcd的倍数就可以了。 #include <bits/stdc++.h> #define sc(...

图论 GCD 思维位运算

2021-01-10

5 765

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

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

二分图图论

2020-12-03

3 785

Graph Coloring I DFS 来自专栏

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

DFS 二分图图论

2020-12-01

5 613

二分图匹配来自专栏

二分图如果能将一个图的点集分为两部分，每一部分内部无边相连，就构成了二分图。所有二分图的题都能用网络流来写。增广路匈牙利算法匈牙利算法是我们很早就接触过的给定男生人数和女生人数，以及他们的互相follow的关系，求最大配对数量。 #include <bits/stdc++....

二分图图论

2020-11-30

3 810

我是 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 744

旋转跳跃 - 并查集

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

图论并查集

2020-07-16

2 621