P1312 畅通工程 - 题解

登录注册上岸

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

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

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

2022年6月30日 12:07

prim

P1312

回复 0 | 赞 3 | 浏览 5.9k

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 | 赞 6 | 浏览 7.2k

#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 | 浏览 9.5k

#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 | 浏览 8.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; ...

1
2

题目畅通工程

题解数量14

发布题解在线答疑

热门题解

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

2 畅通工程 (kruskal + 并查集)题解：

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

4 kruskal(原理讲解）

5 畅通工程题解：

6 最小生成树kruskal模板题

7 畅通工程题解：暴力

8 畅通工程题解：c++

9 畅通工程题解：

10 prim