P1312 畅通工程 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2024年8月19日 16:01

畅通工程题解：请问一下大佬们我哪一步错了，正确率只有25%，我是对着

P1312

回复 2 | 赞 0 | 浏览 353

#include<bits/stdc++.h> using namespace std; int fa[105]; int find(int i) { if(fa[i]==i) return i; fa[i]=find(fa[i]); return fa[i]; } struct node{ int u,v,w; }edge[1...

2024年4月21日 16:27

畅通工程题解：

P1312

回复 0 | 赞 0 | 浏览 458

#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 110, M = 110, INF = 0x3f3f3f3f; int n, m; int p[N]; struct Edge { int a, b, w; bool operator< (const Edge &W)const ...

2024年3月21日 22:14

畅通工程题解：仿Prim算法

P1312

回复 0 | 赞 0 | 浏览 580

#include<bits/stdc++.h> using namespace std; typedef struct Tri { int i; int j; int val; }; int N, M; bool cmp(Tri * a,Tri * b ) { if (a->val < b->val) return true; retu...

2022年6月30日 11:11

kruskal，解释并查集为何可以判断是否成环

P1312

回复 1 | 赞 4 | 浏览 6.0k

#include <iostream> #include <algorithm> using namespace std; const int maxn = 105; int n,m; struct edge{ int u,v,w; } edges[maxn]; // 并查集,用于确定构造最小生成树的过程中，加入一条边后不会生成环 // 原因：并查集里的每一个集合都是一个连通图(或连通分量),如果一条边的两个顶底都在同一个集合中，则加入这条边后必会成环 int fa[maxn]; int _find(int x){ ...

努力努力在努力

2023年2月24日 10:33

kruskal(原理讲解）

P1312

回复 0 | 赞 3 | 浏览 2.9k

//用克鲁斯卡尔算法来求最小生成树（畅通工程）首先，整一个结构体数组来记录两个顶点及花费，按照自定义的sort函数对结构体数组进行排序，然后利用并查集对数组一个个的进行判断两条边是否连通，若未连通，则利用并查集将其连通并且记录花费，同时统计一个增加的边的条数用来判断整个村庄最后是否能连通。 #include <bits/stdc++.h> #include <cmath> #include <cstdio> #include <cstdlib> #include <...

2022年6月30日 12:07

prim

P1312

回复 0 | 赞 1 | 浏览 4.5k

A集合表示已经加入到最小生成树中的点的集合 B集合表示剩下的点的集合 #include <iostream> #include <algorithm> #define INF 1000000 using namespace std; int n,m; const int maxn = 105; // 图 int gra[maxn][maxn]; // dist[i]表示A集合中到B集合中的i点的最短直接距离。特别的，当dist[i]=0意味着i已经在A中了 int dist[maxn]; void p...

2021年4月22日 17:33

最小生成树kruskal模板题

P1312

回复 0 | 赞 0 | 浏览 6.5k

#include<iostream> #include<string> #include<algorithm> #include<vector> using namespace std; const int MAXN = 102; struct Edge{ int a,b; int val; bool operator < (const Edge &A) const{ return val<A.val; } }; Edge edge...

2021年2月27日 23:09

P1312

回复 0 | 赞 0 | 浏览 8.8k

#include <bits/stdc++.h> using namespace std; const int N = 110; struct Edge { int a, b, w; bool operator< (const Edge &W)const{return w < W.w;} }edge[N]; int p[N]; int n, m; int find(int x) { if(p[x] != x) p[x] = find(p[x]); return p[x]; } int main() { whi...

2021年2月18日 18:20

克鲁斯卡尔

P1312

回复 0 | 赞 0 | 浏览 7.2k

#include <iostream> #include <algorithm> using namespace std; const int maxn=1e3; int f[maxn]; struct node{ int x,y,w; }; void init(int n){ for(int i=0;i<=n;i++){ f[i]=i; ...

题目畅通工程

题解数量9

热门题解

1 kruskal，解释并查集为何可以判断是否成环

2 kruskal(原理讲解）

3 prim

4 畅通工程题解：仿Prim算法

5 kruskal算法

6 畅通工程题解：请问一下大佬们我哪一步错了，正确率只有25%，我是对着n诺的题解写的

7 克鲁斯卡尔

8 畅通工程题解：

9 最小生成树kruskal模板题