搜索结果
查询Tags标签： 图论，共有 69条记录-
【图论】——二分图
【图论】——二分图文章目录 【图论】——二分图定义定理二分图判定染色法 二分图最大匹配——匈牙利算法（增广路算法）最大匹配算法思路代码实现定义 *若一张NNN节点无向图可以分为A,BA,BA,B两个交集为空的非空集合，并且同一集合内部的点之间没有连通边，则称该图为二分…
2022/2/7 6:15:44 人评论 次浏览 -
图论算法 待补充
1. 贝尔福特曼 #include<iostream> using namespace std; #include<cstring> #include<cstdio> struct edge {int s, e, v; //起点，终点，边权 }; edge edg[200005]; //存储两次 int n, m, s, ans[100005], cnt; void add_edge(int a, int b, int c) {…
2022/2/6 17:16:57 人评论 次浏览 -
【算法题归纳合集】图论-最小生成树的典型应用
一、AcWing 1140. 最短网络 【题目描述】 农夫约翰被选为他们镇的镇长！ 他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。 约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。 约翰的农场的编号是111，其他农场的编号是2∼n2∼…
2022/2/5 11:42:43 人评论 次浏览 -
图论基础知识
graph： 邻接矩阵（adjacency）: adjacency=[ [0,1,1,0,0,0],[1,0,1,1,0,0],[1,1,0,1,1,0],[0,1,1,0,1,1],[0,0,1,1,0,0],[0,0,0,1,0,0]]度 （degree）： 无向图的度： A：2；B：3 有向图：分为入度和出度 连通图和非连通图 最短路径 度中心性 度中心性=该点的degree / n…
2022/2/4 6:15:47 人评论 次浏览 -
日志2022-2.3
学习内容： 今天学习内容： 1、英语单词100旧+50新 √ 2、英语阅读手译1篇 √ 3、英语单词练字 √ 4、图论算法回顾 √ 5、Java核心技术基础篇回顾（第10章） √ 6、Vue学习笔记回顾 √ 7、SpringBoot回顾 （未完成） 总结 今天事情很满，由于重刷了一遍Acwing的图论基础…
2022/2/3 23:49:30 人评论 次浏览 -
搜索与图论（一）：
DFS、BFS算法及运用 DFS（深度优先搜索） 使用栈来实现，俗称暴搜，最重要的是顺序以及恢复现场 空间复杂度：\(O(h)\) 不具有最短性，适用于比较奇怪且空间要求比较高的题目。 842.排列数字(全排列) 给定一个整数 \(n\) ，将数字 \(1 \sim n\) 排成一排，将会有很多种排列…
2022/1/26 23:35:09 人评论 次浏览 -
图论--最短路的五种算法 适用情况 及 复杂度
稠密图：边多的图： m=n^2（n是点数，m是边数） 只考虑有向图，把无向图当成有向图 Dijkstra:贪心 Floyd：动态规划
2022/1/25 20:04:48 人评论 次浏览 -
AcWing 算法基础课 图论
图可以用邻接表存储， 邻接表为n个链表， 链表可以用数组模拟（比vector速度快）。 const int N; int h[N],e[N],ne[N],idx;//分别表示，h[i]：图中编号i的头结点，e[i]：节点i的值（编号），ne[i]节点i在链表中的下一个节点的idx。 void add(int a,int b) {e[idx]=b;ne[i…
2021/12/26 14:09:59 人评论 次浏览 -
AcWing 算法基础课 图论
图可以用邻接表存储， 邻接表为n个链表， 链表可以用数组模拟（比vector速度快）。 const int N; int h[N],e[N],ne[N],idx;//分别表示，h[i]：图中编号i的头结点，e[i]：节点i的值（编号），ne[i]节点i在链表中的下一个节点的idx。 void add(int a,int b) {e[idx]=b;ne[i…
2021/12/26 14:09:59 人评论 次浏览 -
什么是图?
第一章 什么是图？ 什么是图？ 定义: 图是由若干的顶点（即点或节点）及连接两顶点的边（或线或关系）所构成的图形。 原文: A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines)…
2021/12/21 23:26:18 人评论 次浏览 -
什么是图?
第一章 什么是图？ 什么是图？ 定义: 图是由若干的顶点（即点或节点）及连接两顶点的边（或线或关系）所构成的图形。 原文: A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines)…
2021/12/21 23:26:18 人评论 次浏览 -
图论学习笔记 - 链表与邻接表
链表 1. 前言 C/C++自带的数据结构-数组很好用，但是无法在任意位置插入或删除元素，所以我们就需要另外一种数据结构来实现这种操作，于是链表就诞生了，链表支持在任意位置插入或删除，但只能按顺序依次访问其中的元素。我们可以用一个 struct 表示链表的节点，其中可以…
2021/12/3 23:48:49 人评论 次浏览 -
图论学习笔记 - 链表与邻接表
链表 1. 前言 C/C++自带的数据结构-数组很好用，但是无法在任意位置插入或删除元素，所以我们就需要另外一种数据结构来实现这种操作，于是链表就诞生了，链表支持在任意位置插入或删除，但只能按顺序依次访问其中的元素。我们可以用一个 struct 表示链表的节点，其中可以…
2021/12/3 23:48:49 人评论 次浏览 -
图论综合练习
还是整了一版这一周大致刷的题目，稍有些水了 Contest Balloons CodeForces - 725D 题意： 给一堆队伍，然后每个队伍有气球数和重量数，如果气球数大于重量数，这个队就会起飞（被淘汰），然后在按照气球的多少排名，我们在第一只队伍，我们可以将我们的气球分给别的队，…
2021/11/26 23:10:12 人评论 次浏览 -
图论综合练习
还是整了一版这一周大致刷的题目，稍有些水了 Contest Balloons CodeForces - 725D 题意： 给一堆队伍，然后每个队伍有气球数和重量数，如果气球数大于重量数，这个队就会起飞（被淘汰），然后在按照气球的多少排名，我们在第一只队伍，我们可以将我们的气球分给别的队，…
2021/11/26 23:10:12 人评论 次浏览
