CoolGuang!

图论

atcoder(4) kuangbin刷题记录(9) Task In College(1) 二分查找(5) 位运算(2) 动态规划(10) 博弈论(1) 备忘录(2) 大模拟(7) 字符串算法(3) 思维锻炼(14) 搜索(9) 数据结构(10) 数论(6) 暴力与随机数(3) 未归档(8) 矩阵练习(6) 组合数学(3) 计算几何(1) 计算机知识/辅助工具(1) 贪心算法(4) 路漫漫其修远兮(2) 题解(27)

/ 注册

全部文章 / 图论（共27篇）

图的储存【邻接矩阵，邻接表，优化链式前向星】【图论】【笔记】

图的存储 1.简单储存（邻接矩阵）：第一行输入n与m,表示n个点，m条边然后输入 u,v 表示 u与v相连，代码： int vis[500][500]; void save(int u, int v) { int m,n; scanf("%d%d",&am...

2020-01-13

0 876

求最短路的四种算法【 dijkstra算法】【Floyd算法】【Spfa】【优化Spfa-优先队列】【图论】

首先，何为最短路？假设有五个点，每个点之间都有一条连线，并且赋予距离。给予一对起点与终点，让你求出从起点到终点的最短距离，或者最短时间。 HDU2544. 这个问题可以枚举，从1-2，1-3,1-2-3等等并求出其最短的路线，但是如果数据太多怎么办。假如有1000个点，挨个枚举可能会枚...

2020-01-13

0 763

最短路更新条件的三个变式【总结】【例题】

一、引言 1.求最短路的几种算法，Dijkstra，Floyd，spfa等，总之他们都有一个共同点，就是他们更新的条件一样。条件均为： if(dis[edge[i].e]>dis[u]+len) dis[edge[i].e]=dis[u]+len; dis[edge[i]...

2020-01-13

0 639

求最小生成树【图论】【笔记】

一、定义用大白话来解释就是，用一个图把所有的点都连接起来，而且所有边的总权值在所有图中最小。二、算法 (1)克鲁斯卡尔算法基本思想：第一步：把所有的边从小到大排序。第二步：开始选边，每一个边要保证都不相连，即不能成圈。第三步：判断一下，是不是选了n-1条边，因为...

2020-01-13

0 645

Proving Equivalences&&经典Tarjan算法入门题+缩点

这道题巩固一下Tarjan求强连通分量(最近没有更新图论的算法，天天比赛+总结，等开学就更)，自己写了一下感觉还可以hiahiahia！题目大意：给你几组等价公式问至少还要加几组公式，使得这些公式可以任意之间推出来，比如说a->b,b->c，你只需要加一组c->a就可...

2020-01-13

0 561

2019牛客多校第四场 J free 分层最短路&&模拟建图

链接：https://ac.nowcoder.com/acm/contest/884/J 来源：牛客网时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 524288K，其他语言1048576K 64bit IO Format: %lld 题目描述 Your are give...

2020-01-13

0 508

中石油组队训练赛第一场问题 H: Navy maneuvers 图上dp or 记忆化搜索

(hdu2452) 题目描述 In times of peace, various countries have held regular maneuvers to maintain military’s vigilance. There is a navy fleet in a certain...

2020-01-13

0 438

[kuangbin] Fire Net 二分图最大匹配&行列模型

Suppose that we have a square city with straight streets. A map of a city is a square board with n rows and n columns, each representing a street or a...

2020-01-13

0 471

中石油组队训练赛第五场问题 E: Plug It In! 二分最大匹配

问题 E: Plug It In! 时间限制: 12 Sec 内存限制: 128 MB 提交: 116 解决: 31 [提交] [状态] [命题人:admin] 题目描述 Adam just moved into his new apartment and simply placed ev...

2020-01-13

0 530

2019银川网络赛 F Moving On Floyd 变形算法

问题 F: Moving On 问题 F: Moving On 时间限制: 10 Sec 内存限制: 128 MB 提交: 23 解决: 14 [提交] [状态] [命题人:admin] 题目描述 Firdaws and Fatinah are living in a countr...

2020-01-13

0 616