初始图：采用连通分量的方法，可以有效地避免连通分量的问题。 具体的采用方式是：当某个顶点加到另一个联通分量时，这个顶点的连通分量编号改为更小的那个连通分量编号。 例如：顶点0的连通分量编号是0，顶点5的连通分量编号是5，如果这两个顶点加在一起的话，则顶点5的连通分量编号改为0，这样的话，下次如果还有可能这两条边放在同一连通分量的话，先判断这两个顶点的连通分量是否相同，如果不相同则可以加入这条边，否则不能加...
关键在于并查集的使用#include<cstdio> #include<vector> #include<algorithm> using namespace std;const int maxn = 100; struct edge {int front,end;int value;bool operator < (edge B){if(value < B.value){return true;}else{return false;}} }E[maxn]; int p[maxn]; int find(int x) {if(p[x] == x)return x;else{p[x] = find(p[x]);return p[x];} } //vector<edge>E; int main() {freopen("input.txt","r",stdin);int num...
题目：http://poj.org/problem?id=2349 题目大意：最小生成树找第k大边。 直接Kruskal就把最小生成树跑出来，找第k大边就ok。而我的模板并查集下标从1开始。但是我的点从0开始。导致WA了。 #include<bits/stdc++.h> using namespace std; #define LL long longconst int maxn=1e6+10;struct Edge {int l, r;double v;}edge[maxn];struct F {double x;double y;}f[maxn];int cmp(Edge a, Edge b) {return a.v<b.v; }int cmp1(Edge a...
Prim算法（贪心策略）N^2 选定图中任意定点v0，从v0开始生成最小生成树 树中节点Va，树外节点Vb 最开始选一个点为Va，其余Vb, 之后不断加Vb到Va最短距离的点 1.初始化d[v0]=0，其他d[i]=正无穷。d表示Vb电到i的最小距离 2.经过n次如下步骤，得到一颗喊n节点n-1边的最小生成树 (1)选择一个未标记的k，并且d[k]的值最小 (2)标记点k进入树Va (3)以k为中间点，修改未标记的点j，即Vb中的点到Va的距离值； 3.得到最小生成树t#include<io...
上一期说完了什么是最小生成树，这一期咱们来介绍求最小生成树的算法：kruskal算法，适用于稀疏图，也就是同样个数的节点，边越少就越快，到了数据结构与算法这个阶段了，做题靠的就是速度快，时间复杂度小。网上一搜就知道大家都会先介绍prim算法，而我为什么不介绍prim算法呢？因为小编认为这个算法理解快，也很容易明白，可以先做个铺垫（小编绝不会告诉你小编是因为不会才不说的），kruskal算法核心思想是将一棵棵树林（也可以...
无向加权图 1.生成树(minimum spanning trees)图的生成树是它一棵含有所有顶点的无环联通子图最小生成树:生成树中权值和最小的(所有边的权值之和)Prim算法、Kruskal算法就是实现最小生成树的算法 2.Prim算法应用前提:权值各不相同的连通子图(权值相同,最小生成树不唯一)
一、 最小生成树 在含有n个顶点的连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。 例如，对于如上图G4所示的连通网可以有多棵权值总和不相同的生成树。 二、克鲁斯卡尔算法介绍 克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。 基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。 具体做法：首先构造一个只...
1596.最少修建多长的公路能把所有村庄连起来（一） 时限：1000ms 内存限制：10000K 总时限：3000ms 描述 一个地区有n个村庄，有一些村子之间可以修路，已知每条路的长度，问最少修建多长的公路可以把所有的村子连接起来。 输入 先输入两个正整数n，m(n小于10000，m小于100000)，表示有n个村庄，m条可以修建的路，接下来的m行每行三个整数，前两个表示村庄的编号（0~n-1），第三个表示这条路的长度。 输出 输出路的总长度的最小值。...
#include <bits/stdc++.h> using namespace std;const int maxn = 5e5 + 10; int h[maxn], v[maxn], nx[maxn], in[maxn]; int n, m, sz;void add(int a, int b) {v[sz] = b;nx[sz] = h[a];h[a] = sz;in[b] ++;sz ++; }void init() {for(int i = 1; i <= n; i ++) {h[i] = -1;in[i] = 0;}sz = 0; }void work() {queue<int> Q;vector<int> ans;for(int i = 1; i <= n; i ++) {if(in[i] == 0) {Q.push(i);}}while(!Q.empty()) {int tp...
Prim算法（使用visited数组实现） Prim算法求最小生成树的时候和边数无关，和顶点树有关，所以适合求解稠密网的最小生成树。 Prim算法的步骤包括： 1. 将一个图分为两部分，一部分归为点集U，一部分归为点集V，U的初始集合为{V1}，V的初始集合为{ALL-V1}。 2. 针对U开始找U中各节点的所有关联的边的权值最小的那个，然后将关联的节点Vi加入到U中，并且从V中删除（注意不能形成环）。 3. 递归执行步骤2，直到V中的集合为空。 4. U中...