P1341 还是畅通工程 - 题解

登录注册上岸

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

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

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

2025年3月24日 11:02

还是畅通工程题解：暴力

P1341

回复 0 | 赞 0 | 浏览 262

#include <bits/stdc++.h> using namespace std; //思路：最小生成树，直接k算法贪心了，记得要用并查集 int fd[105]; int find(int n) { if(fd[n]==n)return n; return find(fd[n]); } struct node { int start; int ed; &nb...

2025年3月14日 13:29

还是畅通工程题解：并查集优化实现的最小生成树问题

P1341

回复 0 | 赞 1 | 浏览 252

#include <bits/stdc++.h> using namespace std; struct road{ int a,b,w; road(int a,int b,int w):a(a),b(b),w(w){} bool operator <(road y){ return w<y.w; } }; vector<int>f; int findroot(int x){ return f[x]==x?x:f[x]=findroot(f[x]); } ...

2024年8月2日 00:29

Prim构造最小生成树

P1341

回复 0 | 赞 0 | 浏览 686

#include<iostream> using namespace std; const int INF = 1000000; const int N = 105; int g[N][N]; int v[N]; int n, m; void func(){ m = (n*(n-1))/2; for(int i=0;i<=n;i++){ v[i] = INF; } for(int i=0;i<=n;i++){ for(int j=0;j<...

2024年6月26日 22:36

牛客能通过全部用例，N诺只有80%

P1341

回复 1 | 赞 1 | 浏览 618

牛客能通过全部用例，N诺只有80% #include<bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; const int N = 105; int mpt[N][N]; int minDist[N]; int main(){ int n; while(cin >> n){ memset(mpt, 0, sizeof(mpt)); memset(minDist, 0x3f, sizeof(minDist)); if(n ...

2024年3月18日 18:34

还是畅通工程题解：

P1341

回复 0 | 赞 1 | 浏览 658

#include <bits/stdc++.h> using namespace std; const int maxn=105; int fa[maxn]; struct node{ int n1,n2,km; }edge[maxn*maxn]; int cmp(node a,node b){ return a.km<b.km; } int find(int x){ if(x==fa[x]) return x; &nbs...

2024年3月12日 10:40

还是畅通工程题解：简单的

P1341

回复 0 | 赞 1 | 浏览 893

#include<iostream> #include<algorithm> #include<string> #include<string.h> using namespace std; //定义结点之间的连接信息 struct node { int x; int y; int fee; }; int fa[100];//记录结点的自己的父亲 int sum = 0,ans=0, n;//记录总建路数 struct no...

2023年1月16日 14:43

kruskal（并查集板子题）

P1341

回复 0 | 赞 3 | 浏览 4.2k

#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10, M = 2e5 + 10, INF = 0x3f3f3f3f; int n, m; int p[N]; struct Edge { int a, b, w; bool operator<(const Edge &e) const { return w < e.w; } } es[M]; int find(int x) { ...

2021年2月18日 19:37

克鲁斯卡尔

P1341

回复 0 | 赞 0 | 浏览 7.6k

#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; ...

题目还是畅通工程

题解数量8

发布题解在线答疑

热门题解

1 kruskal（并查集板子题）

2 还是畅通工程题解：简单的

3 牛客能通过全部用例，N诺只有80%

4 还是畅通工程题解：

5 还是畅通工程题解：并查集优化实现的最小生成树问题

6 Prim构造最小生成树

7 还是畅通工程题解：暴力

8 克鲁斯卡尔