搜索结果
查询Tags标签： Edges，共有 49条记录-
ABC263 G - Erasing Prime Pairs
拆点 + 最大流 G - Erasing Prime Pairs (atcoder.jp) 题意 有 n（n <= 100）种互不相同的数，分别是 \(A[i]\) （<=1e7）, 每个有 \(B[i]\) 个 每次可以任意取两个数，如果相加是素数就消去这两个数，求最多操作次数 思路 思路一、不考虑 1 + 1 = 2 出现偶素数，可…
2022/9/8 23:53:09 人评论 次浏览 -
克鲁斯卡尔(Kruskal)算法
1.应用场景-公交站问题1)某城市新增7个站点(A, B, C, D, E, F, G) ，现在需要修路把7个站点连通 2)各个站点的距离用边线表示(权) ，比如 A – B 距离 12公里 3)问：如何修路保证各个站点都能连通，并且总的修建公路总里程最短? 2.克鲁斯卡尔算法介绍 1)克鲁斯卡尔(Krusk…
2022/9/3 14:24:05 人评论 次浏览 -
[LeetCode] 2374. Node With Highest Edge Score
You are given a directed graph with n nodes labeled from 0 to n - 1, where each node has exactly one outgoing edge. The graph is represented by a given 0-indexed integer array edges of length n, where edges[i] indicates that there is a directed edge f…
2022/8/15 1:53:55 人评论 次浏览 -
Kruskal 算法
Kruskal 算法 1.Kruskal 算法介绍 最小生成树： 给定一张边带权的无向图 \(G=(V,E)\)，其中 \(V\) 表示图中点的集合，\(E\) 表示图中边的集合，\(n=|V|\)，\(m=|E|\)。 由 \(V\) 中的全部 \(n\) 个顶点和 \(E\) 中 \(n-1\) 条边构成的无向连通子图被称为 \(G\) 的一棵生成…
2022/7/25 1:52:55 人评论 次浏览 -
凸包和网络流模板
凸包模板 这题是整数范围，需要时请改浮点数 #include<bits/stdc++.h> #define int long long using namespace std; const int maxn=5110; int n; struct node{int x,y; }s[maxn],e[maxn]; int top; inline int area(node a1,node a2,node b1,node b2){return (a2.…
2022/7/9 23:22:17 人评论 次浏览 -
leetcode 310. Minimum Height Trees 最小高度树(中等)
一、题目大意 标签: 搜索 https://leetcode.cn/problems/minimum-height-trees 树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。 给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 …
2022/6/13 23:22:43 人评论 次浏览 -
二分图完全匹配 不完全匹配 / linear_sum_assignment 详解
https://jack.valmadre.net/notes/2020/12/08/non-perfect-linear-assignment/\(G = (U,V,E)\)\(|U| = r\) \(|V| = n\) without loss of generality, assume \(r \leq n\)\[\begin{bmatrix} \infty & 3 & -1 \\ \infty & 5 & \infty \\ 2 & -3 &…
2022/4/17 23:18:24 人评论 次浏览 -
684. 冗余连接
684. 冗余连接 树可以看成是一个连通且 无环 的 无向 图。给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示…
2022/4/4 6:20:27 人评论 次浏览 -
最小生成树和二分图
Prim 与dijistra比较像，分为朴素版和堆优化版。 朴素版Prim，时间复杂度O(n^2)，一般用于稠密图。 算法流程：初始化距离矩阵为0x3f3f3f3f. 循环n次，找到距离集合最短的点t，用t更新其他点到集合的距离。 注意：与dijistra不同的在与距离的更新方式。 Prim最小生成树 #i…
2022/2/25 23:51:20 人评论 次浏览 -
Summer Earnings
在一个平面内给出nn个点的坐标，任选其中三个为圆心作半径相同的圆，要求这三个圆不能相交但可以相切，求能画出的圆中的最大半径。 分析 待补充 AC import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arr…
2022/2/13 23:46:44 人评论 次浏览 -
图论基础知识
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 人评论 次浏览 -
AcWing859 kruskal算法求最短路
#include<iostream> #include<algorithm> using namespace std; const int N = 2e5 + 10; int n, m; int p[N];struct edge {int a, b, w;bool operator< (const edge& W)const{return w < W.w;} }; edge edges[N];int find(int x) {if (x != p[x])…
2022/1/30 14:04:55 人评论 次浏览 -
2045. 到达目的地的第二短时间_2022_01_22
2045. 到达目的地的第二短时间 城市用一个 双向连通 图表示，图中有 n 个节点，从 1 到 n 编号（包含 1 和 n）。图中的边用一个二维整数数组 edges 表示，其中每个 edges[i] = [u<sub style="display: inline;">i</sub>, v<sub style="dis…
2022/1/24 23:08:28 人评论 次浏览 -
43.Kruskal算法
public class KruskalCase {private int edgeNum; //边的个数private char[] vertexs; //顶点数组private int[][] matrix; //邻接矩阵//使用 INF 表示两个顶点不能连通private static final int INF = Integer.MAX_VALUE;public static void main(String[] args) {char[]…
2022/1/17 9:04:24 人评论 次浏览 -
43.Kruskal算法
public class KruskalCase {private int edgeNum; //边的个数private char[] vertexs; //顶点数组private int[][] matrix; //邻接矩阵//使用 INF 表示两个顶点不能连通private static final int INF = Integer.MAX_VALUE;public static void main(String[] args) {char[]…
2022/1/17 9:04:24 人评论 次浏览
