搜索结果
查询Tags标签： 图论，共有 69条记录-
【牛客小白月赛70】A-F题解【小d和超级泡泡堂】【小d和孤独的区间】【小d的博弈】【小d和送外卖】
比赛传送门：https://ac.nowcoder.com/acm/contest/53366 难度适中。🎈 作者：Eriktse 🎈 简介：19岁，211计算机在读，现役ACM银牌选手🏆力争以通俗易懂的方式讲解算法！❤️欢迎关注我，一起交流C++/Python算法。（优质好文持续更新中……）🚀 🎈 阅读原文获得…
2023/4/8 14:52:02 人评论 次浏览 -
图论
多源最短路（在曼哈顿图中）（无例题）（使用BFS，队列）：操作的地图要有两个特点：既可以表示结果中所要的最短距离，又能记录这个点是否走过，那就全部memset为一个特殊的数-1（这里一定要专门设计一个结果图，不能只用最初的图，让最初的图承担三个责任，它哪里做的到…
2022/9/1 23:26:03 人评论 次浏览 -
一个图论很好用的软件
Graphviz 新版本似乎没有自带的编辑器了,老版本有可以点此下载安装完成后在目录\bin下找gvedit.exe即可 使用教程可以官网文档或者B乎 简单的几个例子 无向图有向图改颜色和标签有向环推荐 https://www.cnblogs.com/shuqin/p/11897207.html
2022/8/15 6:26:36 人评论 次浏览 -
图论-虚拟节点分层建图
图论-虚拟节点分层建图 Nya图最短路 题目链接:Virtual Judge Acwing题意: 题解:\(a,b\)连一个\(w\)的边,是正常操作,这里有一个重要操作是\(a\)层和\(a+1\)层能直接传送,如果这里使用笨笨的建图方式,那么时间复杂度就是\(O(n^2)\),时间复杂度太高,不太行.这里有一个聪明的…
2022/8/4 6:25:39 人评论 次浏览 -
图论——最小生成树——Prim
最小生成树与最短路比较相像，解决的问题也比较相像，尤其是今天说的Prim算法，它和Dijkstra十分相似。 Prim比较简单，这篇会用最简洁的语言概括到它的精髓，简洁易懂。 重要的事情说三遍：Prim算法适用于稠密图。 重要的事情说三遍：Prim算法适用于稠密图。 重要的事情说…
2022/7/23 23:27:05 人评论 次浏览 -
图论 Graph Theory
Graph Theory 图论 Laplacian matrix Categories of graphs:directed/undirected. homogeneous/heterogeneous. static/dynamic. A dynamic graph is a graph whose topology varies with time.It is a matrix representation of a graph. It can be used: (1) to constru…
2022/7/7 6:20:18 人评论 次浏览 -
图论：Ford 算法 求最短路径
Ford 算法 求最短路径先构建邻接表数组和初始化邻接关系int v1[maxn],v2[maxn],w[maxn];//记录起点终点和权值for(int i=1;i<=m;++i){cin>>u>>v>>val;v1[i]=u;v2[i]=v;w[i]=val;}构建一维数组d，记录距离出发点的距离，d[出发点]初始化为0，自己和自…
2022/5/10 17:00:31 人评论 次浏览 -
图论最短路算法
图论最短路讲的并不是两点之间线段最短，对于有向图or无向图来讲，最短路表示的路径上（边上）权值和的大小，如果是最小，我们称这是图的最短路； 最短路算法大致分：多对多，单对多，单对单； 而根据算法的类型不同，图的最短路算法有这三种算法：floyd-warshall,bellma…
2022/4/25 9:14:51 人评论 次浏览 -
图论习题及答案
A - Graph 例题链接： https://vjudge.net/contest/490112#problem/A 题目来源： https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_A 题目思路： 给你一个无向图的很多串邻接链表，你需要将这些邻接链表转换成邻接矩阵的形式 容易Presentation erro…
2022/4/24 6:15:34 人评论 次浏览 -
图论-最小生成树-贪心
最小生成树 概念 在所有图所形成的生成树中边权值最小的 生成树条件： 1.包含联通图的n个顶点，n-1条边 2.移除任何一条边都会导致不联通 3.生成树中不包括环 堆优化的prim算法（vector模拟邻接表） prim要素 任意从一个点开始，每次选出一个未用点到已用点最短的点，以此…
2022/4/22 23:13:49 人评论 次浏览 -
算法学习-图论-图的存储-最短路
题目概述及细节 单源最短路，模板，luoguP3371 单源最短路，模板 dij算法 核心是把节点分为两类，一类是以确定到起点最短的距离，一类是没有确定初始时所有都未确定 从没有确定的节点中选取一个距离起点最短的 依据此点确定别的未更新的点的距离 首先补充题目中常见的数值…
2022/4/19 11:13:05 人评论 次浏览 -
第2章 图论基础
简介 本章将主要介绍以下内容：图的表示 图的性质 复杂图 图上的计算任务图的表示图的定义：一个图可以被表示为\(G = \{V, E\}\)，其中\(V = \{v_1, \dots, v_N\}\)是大小为\(N = |V|\)的节点集合，\(E = \{e_1, \dots, e_M\}\)是大小为\(M\)的边的集合。注意：在没有特殊…
2022/4/2 23:21:11 人评论 次浏览 -
第62期：图论-最小生成树-Boruvka算法
参考： Boruvka算法 - lher - 博客园 Boruvka算法_weixin_30527323的博客-CSDN博客 最小生成树的Boruvka算法__shivering_的博客-CSDN博客_boruvka算法 【模板】最小生成树题解 - 洛谷 1.【模板】最小生成树 - 洛谷#include<bits/stdc++.h> using namespace std; co…
2022/3/18 20:28:08 人评论 次浏览 -
图论 *最短路*
多源最短路：Floyd 所谓多源，就是求图中任意两点的最短路。 floyd是一种动态规划的做法。 首先我们给出状态定义：$f(i,j,k)$ 表示除了点$i j$外，只经过$1~k$个点， $i$到$j$的最短路，不难得出状态转移方程：$ f(i,j,k) = min(f(i,k,k-1)+f(k,j,k-1)) $ 优化掉$k$那一维…
2022/2/16 23:12:23 人评论 次浏览 -
【准备5】基础图论问题
P1194 买礼物 Problem Link solution \(\quad\)这玩意的本质就是最小生成树。如果 a 对 b 有优惠，那么我们将 a 向 b 连一条边，然后将 0 向所有节点连一条权值为 A 的边，最后跑一遍最小生成树即可。 code #include<bits/stdc++.h>using namespace std; struct no…
2022/2/15 6:13:42 人评论 次浏览
