Izayoi_w

未归档

2019牛客多校(3) bfs(1) csdn博客(1) c语言(1) 个人刷kuangbin带你飞系列(3) 原创(4) 图论学习(1) 数论(1) 计算机(1) 转载(1)

/ 注册

全部文章 / 未归档（共34篇）

kuangbin八A：POJ 1679 The Unique MST（次小生成树）

Description: Given a connected undirected graph, tell if its minimum spanning tree is unique. Definition 1 (Spanning Tree): Consider a connected, un...

2018-08-09

0 550

次小生成树

转同学的一个模板链接：https://blog.csdn.net/chenshibo17/article/details/81215933 细分了带重边和不带重边的。次小生成树定义：设 G=(V,E,w)是连通的无向图，T 是图G 的一个最小生成树。如果有另一棵树T1，满足不存在树T’,ω（T...

2018-08-09

0 546

生成树计数与Matrix-Tree定理

生成树计数问题：对于一个有n个点的无向图，由图中n-1条边构成一个边集，这n-1条边恰好连接图中全部的点并构成一棵树，称为生成树，求这样的边集的个数。从上面的描述中，我们知道两个不同的生成树之间是允许有重复的边的，比如：他就有三个生成树： Matrix-Tree定理：预备概...

2018-08-09

0 809

数学应用模板：求行列式

本贴是用于求行列式的模板贴。按行（列）展开递归求行列式特点：对于int型该方法是封闭的，所有过程可全部用int型完成，不需要转换成double，当然double型也可以用。 struct Matrix { int matrix[MAXN][MAXN] = {{0}}; in...

2018-08-08

0 498

kuangbin六A：POJ 1251 Jungle Roads（最小生成树模板题）

Description：模板题没啥好说的 prim： #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace...

2018-08-08

0 506

最小生成树Prim算法与Kruskal算法

这两种算法是基于不同的角度得出的最小生成树算法，Prim是“加点法”，而Kruskal是“加边法”。下面让我们来看一看这两种算法的原理和具体实现。相关概念：连通图：在无向图中，若任意两个顶点与都有路径相通，则称该无向图为连通图。强连通图：在有向图中，若任意两个顶点与都有路径相通，...

2018-08-08

0 962

寂静之城

链接：https://www.zhihu.com/question/277522256/answer/396613033 来源：知乎著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。原作：马伯庸寂静之城美利坚合众国，2015年，纽约。　　当电话响起来的时候，阿...

2018-08-05

0 7814

kuangbin带你飞系列目录与简介

kuangbin带你飞系列是由ACM圈内的一个菊苣，上海大学的邝斌（现已研究生毕业，就职于谷歌），在vjudge平台上建立的一个题目系列，从最简单的暴力搜索，到各种高深的算法与数据结构，几乎无所不包，这一套刷下来对于每一位打ACM的人来说都将是一次水平的飞跃。目录链接：https://cn.vj...

2018-08-05

1 2033

kuangbin五A：POJ2236 Wireless Network（并查集应用）

Description： An earthquake takes place in Southeast Asia. The ACM (Asia Cooperated Medical team) have set up a wireless network with the lap computer...

2018-08-03

0 472

并查集的实现及优化

并查集是一种用于在森林中判断子图数量及点的归属的数据结构，由于其特殊的路径压缩操作，使得这一过程可以异常地快。并查集主要由一个pre数组以及两个函数组成：find函数和join函数。 pre数组表示每一节点的前驱，最终已完成的并查集，每一个子图的所有点只有一个前驱（这也是其高效的原因），而初始化...

2018-08-03

0 504