亮亮解出了卷轴隐藏的秘密，来到了一片沼泽地。这里有很多空地，而面试直通卡可能埋在任意一块空地中，好在亮亮发现了一堆木材，他可以将木材铺在两个空地之间的沼泽地上。因为亮亮不知道面试直通卡具体在哪一块空地中，所以必须要保证任意一块空地对于亮亮来说是可以抵达的。
“怎么还有鳄鱼！没办法，看来有些空地不能直接到达了。” 亮亮虽然没有洁癖，但是沼泽地实在太臭了，所以亮亮不会循环利用木材。而且木材不能拼接在一起使用，所以亮亮必须要知道在耗费木材最少的情况下，最长的那根木材至少需要多长。
[编程题]寻宝
//使用Cruskal解决问题
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
//并查集实现最小生成树
public class Main{
private static class Edge{
//起点和终点
int x,y;
int weight;
public Edge(int x,int y,int weight)
{
this.x=x;
this.y=y;
this.weight=weight;
}
}
public static int father(int i,int a[])
{
int k=i;
while(a[k]!=k)k=a[k]; //并查集
return k;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in=new Scanner(System.in);
while(in.hasNext())
{
int n=in.nextInt();
int m=in.nextInt();
Edge[] edges=new Edge[m];
for(int i=0;i<m;i++)
{
edges[i]=new Edge(in.nextInt(),in.nextInt(),in.nextInt());
}
int a[]=new int[n+1];
for(int j=0;j<=n;j++)
{
a[j]=j;
}
Arrays.sort(edges,new Comparator<Edge>() {
@Override
public int compare(Edge o1, Edge o2) {
// TODO Auto-generated method stub
return o1.weight-o2.weight;
}
});
int res=0;
for(int i=0;i<m;i++)
{
int px=father(edges[i].x,a);
int py=father(edges[i].y,a);
if(px!=py)
{
if(edges[i].weight>res)res=edges[i].weight;
if(px>py)
a[px]=py;
else
a[py]=px;
}
}
System.out.println(res);
}
}
}
发表于 2016-08-11 18:43:17
回复(5)
图的最小生成树 Prim算法或者Kruscal算法
下面给出Prim算法解法
如图所示 此例最小木材铺法如图最后步骤所示
此时最长木板为5
算法思想：
从V1出发 求出所有点中与V1的距离最短的一个节点V3(无法与V1直接相连的距离为无穷) 得到第一条边 然后在求剩下点到V1和V3的距离最近的点V6 依次类推直到所有点用完
注意：
为了减少时间复杂度引入数组dis[] dis[i]表示节点i到已连接的集合中所有点的最小距离
一开始时只有V1在集合中 所以dis[i]就为每个点到V1的距离 当V3也加入时 dis[i]要更新为
min(i到V1的距离， i到v3的距离)后面依次类推
这样可以将总的时间复杂度降为O(n^2)
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1e4 + 1;
const int MAX_INT = INT_MAX;
int dis[maxn];
int n, m, taken[maxn];
struct Node{
int to, val;
Node(int a, int b){
to = a;
val = b;
}
};
vector v[maxn];
int main(){
while(scanf("%d%d", &n, &m) == 2){
memset(taken, 0, sizeof(taken));
memset(dis, 0, sizeof(dis));
for(int i = 0; i < m; i++){
int a, b, val;
scanf("%d%d%d", &a, &b, &val);
v[a].push_back(Node(b, val));
v[b].push_back(Node(a, val));//用vector保存图
}
taken[1] = 1;//从点1开始
//由于鳄鱼的存在(即存在非联通分量 即存在从1出发永远到不了的点 所以必须从1出发 舍弃到不了的点)
for(int i = 1; i <= n; i++) dis[i] = MAX_INT;
for(int i = 0; i < v[1].size(); i++) dis[v[1][i].to] = v[1][i].val; //每个点到点1的距离
int ans = 0;
for(int i = 1; i < n; i++){
int min_val = MAX_INT, min_p;
for(int j = 1; j <= n; j++){//每个点到已连接集合的最短距离
if(!taken[j] && dis[j] < min_val){
min_val = dis[j];
min_p = j;
}
}
if(min_val == MAX_INT) continue;
ans = max(ans, min_val);
taken[min_p] = 1;
for(int j = 0; j < v[min_p].size(); j++){//更新dis数组
if(!taken[v[min_p][j].to] && v[min_p][j].val < dis[v[min_p][j].to])
dis[v[min_p][j].to] = v[min_p][j].val;
}
}
cout<<ans<<endl;
for(int i = 0; i < n; i++) v[i].clear();
}
return 0;
}
/*
4 3
1 2 1
2 3 1
3 4 2
ans： 2
5 4
1 2 3
1 3 8
2 3 2
4 5 7
ans: 3
*/
编辑于 2018-10-28 15:50:00
回复(0)
//循边最小生成树，并查集动态查询连通性
include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <map>
using namespace std;
int father(int i, vector<int> &UF)
{
int k=i;
while(UF[k]!=k)k=UF[k];
return k;
}
int main()
{
int N,M;
while(cin>>N>>M)
{
multimap<int,pair<int,int>> cost;
while(M--)
{
int a,b,c;
cin>>a>>b>>c;
cost.insert(make_pair(c,make_pair(min(a,b),max(a,b))));
}
vector<int>UF(N+1);
for(int i=0;i<=N;i++)
UF[i]=i;
int maxV = -1;
int cc = 0;
for(auto it=cost.begin();it!=cost.end();it++)
{
int px = father(it->second.first,UF);
int py = father(it->second.second,UF);
if(px != py)
{
cc++;
if(it->first>maxV)maxV=it->first;
UF[px] = UF[py];
}
}
cout<<maxV<<endl;
};
return 0;
}
编辑于 2016-08-20 09:03:46
回复(2)
本套6道题全部pass的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions)
牛客网上的其他题目解答也在持续更新。
【题解】贪心算法：每次添加最短的木块，直到全连通。使用并查集判断动态连通性。
#include <iostream>
#include <algorithm>
using namespace std;
struct Wood
{
unsigned short int P, Q, K;
};
bool cmp(Wood wood1, Wood wood2);
int find(int *set, int x);
int main()
{
int N, M; cin >> N >> M;
Wood *wood = new Wood[M];
int maxLen = 0;
for (int i = 0; i < M; i++) {
cin >> wood[i].P >> wood[i].Q >> wood[i].K;
wood[i].P -= 1;
wood[i].Q -= 1;
}
sort(wood, wood + M, cmp);
int *set = new int[N];
for (int i = 0; i < N; i++) {
set[i] = i;
}
for (int i = 0; i < M; i++) {
int fx = find(set, wood[i].P);
int fy = find(set, wood[i].Q);
set[fx] = fy;
int cnt = 0;
for (int i = 0; i < N; i++) {
cnt += set[i] == i ? 1 : 0;
}
if (cnt == 1) {
cout << wood[i].K;
delete[] wood;
return 0;
}
}
}
bool cmp(Wood wood1, Wood wood2)
{
return wood1.K < wood2.K;
}
int find(int *set, int x){
return x == set[x] ? x : (set[x] = find(set, set[x]));
}
发表于 2018-03-20 11:29:18
回复(1)
如果用prime,图的构建用邻接矩阵会超限，请用邻接表
package com.special.first;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
/**
* 楚楚街02-寻宝
*
* 最小生成树，保留最大的边的即可
* prime算法，不过我用邻接矩阵超内存限制了，后改用邻接表
*
* Create by Special on 2018/3/9 10:26
*/
public class Pro057 {
static final int MAX = Integer.MAX_VALUE;
static final int MIN = Integer.MIN_VALUE;
// public static int getMaxTree(int N, int[][] costs){
// int[] prices = new int[N];
// Arrays.fill(prices, MAX);
// boolean[] visited = new boolean[N];
// for(int i = 0; i < N; i++){
// if(costs[0][i] != MAX){
// prices[i] = costs[0][i];
// }
// }
// visited[0] = true;
// int index, min, maxTree = MIN;
// for(int i = 1; i < N; i++){
// index = -1;
// min = MAX;
// for(int j = 1; j < N; j++){
// if(!visited[j] && prices[j] < min){
// index = j;
// min = prices[j];
// }
// }
// maxTree = Math.max(maxTree, min);
// visited[index] = true;
// for(int j = 1; j < N; j++){
// if(!visited[j] && costs[index][j] != MAX
// && costs[index][j] < prices[j]){
// prices[j] = costs[index][j];
// }
// }
// }
// return maxTree;
// }
static class Node{
int drc;
int cost;
public Node(int drc, int cost){
this.drc = drc;
this.cost = cost;
}
}
public static int getMaxTree(int N, ArrayList<Node>[] costs) {
int[] prices = new int[N];
Arrays.fill(prices, MAX);
boolean[] visited = new boolean[N];
for (int i = 0; i < costs[i].size(); i++) {
prices[costs[i].get(i).drc] = costs[i].get(i).cost;
}
visited[0] = true;
int index, min, maxTree = MIN;
for (int i = 1; i < N; i++) {
index = -1;
min = MAX;
for (int j = 1; j < N; j++) {
if (!visited[j] && prices[j] < min) {
index = j;
min = prices[j];
}
}
maxTree = Math.max(maxTree, min);
visited[index] = true;
ArrayList<Node> head = costs[index];
int drc;
for (int j = 0; j < head.size(); j++) {
drc = head.get(j).drc;
if (!visited[drc]) {
prices[drc] = Math.min(prices[drc], head.get(j).cost);
}
}
}
return maxTree;
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while(input.hasNext()){
int N = input.nextInt();
int M = input.nextInt();
// int[][] costs = new int[N][N];
ArrayList<Node>[] costs = new ArrayList[N];
for(int i = 0; i < N; i++){
costs[i] = new ArrayList<>();
}
int src, drc, cost;
while(M-- > 0){
src = input.nextInt() - 1;
drc = input.nextInt() - 1;
cost = input.nextInt();
costs[src].add(new Node(drc, cost));
costs[drc].add(new Node(src, cost));
}
System.out.println(getMaxTree(N, costs));
}
}
}
发表于 2018-03-09 11:24:07
回复(0)
没有想到最小生成树，用的DFS,超时。
#include <bits/stdc++.h>
using namespace std;
unordered_map<int, vector<pair<int, int>>> umap;
bool visited[10001];
unsigned long long sum = 0;
int maxK = -1, premaxK = -1, ans = -1;
bool isLeaf = false;
void dfs(int N, int pos, int count) {
if(count == N-1) {
cout << "sum = " << sum << endl;
ans = max(ans, maxK);
maxK = premaxK;
return;
}
bool flag = false;
for(int i = 0; i < umap[pos].size(); ++i) {
if(!visited[umap[pos][i].first]) {
flag = true;
visited[umap[pos][i].first] = true;
sum += umap[pos][i].second;
premaxK = maxK;
maxK = max(maxK, umap[pos][i].second);
dfs(N, umap[pos][i].first, count+1);
if (isLeaf) {
isLeaf = false;
sum += umap[pos][i].second;
count += 1;
dfs(N, pos, count);
count -= 1;
maxK = premaxK;
visited[umap[pos][i].first] = false;
sum -= 2*umap[pos][i].second;
} else {
maxK = premaxK;
visited[umap[pos][i].first] = false;
sum -= umap[pos][i].second;
}
}
}
if(!flag) {
isLeaf = true;
}
}
int main() {
int N, M;
while (cin >> N >> M) {
//memset(table, 0, sizeof(table));
memset(visited, 0, sizeof(visited));
for (int i = 0; i < M; ++i) {
int P, Q, K; cin >> P >> Q >> K;
//table[P-1][Q-1] = K;
//table[Q-1][P-1] = K;
umap[P-1].push_back(make_pair(Q-1, K));
umap[Q-1].push_back(make_pair(P-1, K));
}
visited[0] = true;
dfs(N, 0, 0);
cout << ans << endl;
}
return 0;
}
最小生成树代码：
int bin[10001];
void init() {
for (int i = 0; i <= 10000; i++) {
bin[i] = i;
}
}
int findx(int x) {
int r = x;
while ( r != bin[r]) r = bin[r];
return r;
}
int main() {
int n, m;
while (cin >> n >> m) {
multimap<int, pair<int, int>> mmap;
for (int i = 0; i < m; i++) {
int p, q, k; cin >> p >> q >> k;
mmap.insert(make_pair(k, make_pair(min(p, q), max(p, q))));
}
init();
int maxK = -1;
for (auto &item : mmap) {
int fx = findx(item.second.first);
int fy = findx(item.second.second);
if (fx != fy) {
bin[fy] = fx;
maxK = max(maxK, item.first);
}
}
cout << maxK << endl;
}
return 0;
}
不过值得注意的是，默认输入数据是保证图是联通的，如果输入数据使得图不连通，那么此时需要对这些特殊输入作处理，比如输出-1啥的，表示不可到达。不过测试用例没有这种不连通的输入。建议加上这些测试用例。
修改后的代码如下：
int bin[10001];
bool mark[10001];
void init() {
for (int i = 0; i <= 10000; i++) {
bin[i] = i;
mark[i] = false;
}
}
int findx(int x) {
int r = x;
while ( r != bin[r]) r = bin[r];
return r;
}
int main() {
int n, m;
while (cin >> n >> m) {
multimap<int, pair<int, int>> mmap;
for (int i = 0; i < m; i++) {
int p, q, k; cin >> p >> q >> k;
mark[p] = mark[q] = true;
//mmap.insert(make_pair(k, make_pair(min(p, q), max(p, q))));
mmap.insert(make_pair(k, make_pair(p, q)));
}
init();
int maxK = -1;
for (auto &item : mmap) {
int fx = findx(item.second.first);
int fy = findx(item.second.second);
if (fx != fy) {
bin[fy] = fx;
maxK = max(maxK, item.first);
}
}
int cc = 0;
for(int i = 1; i <= 10000; i++) {
if (bin[i] == i && mark[i]) cc++;
}
if (cc > 1)
cout << "invalid input" << endl;
else
cout << maxK << endl;
}
return 0;
}
编辑于 2017-05-11 16:03:59
回复(0)
#include <bits/stdc++.h>
using namespace std;
int parent(int i, vector<int> &a)
{ int k = i; while(a[k] != k) k = a[k]; return k;
}
int main()
{ int N,M; while(cin>>N>>M) { multimap<int,pair<int,int>> cost; while(M--) { int p,q,k; cin>>p>>q>>k; cost.insert(make_pair(k, make_pair(min(p,q), max(p,q)))); } vector<int> a(N+1); for(int i=0;i<=N;i++) a[i] = i; int maxV = -1; for(auto it=cost.begin();it!=cost.end();it++) { int px = parent(it->second.first, a); int py = parent(it->second.second, a); if(px != py) { if(it->first > maxV) maxV = it->first; a[px] = a[py]; } } cout<<maxV<<endl; } return 0;
}
发表于 2017-11-28 00:55:21
回复(0)
import java.util.Scanner;
public class Main {
public static class Dis{
int index; //空地的起点
int dis; //空地的终点
int pre; //两块空地之间的距离
}
public static void main(String args[]){
Scanner cin = new Scanner(System.in);
while(cin.hasNext()){
int n = cin.nextInt();
int m = cin.nextInt();
Dis map[] = new Dis[m];
for(int i = 0;i < m;i++){
map[i] = new Dis(); //每次进入的元素插入队尾
map[i].index = cin.nextInt();
map[i].pre = cin.nextInt();
map[i].dis = cin.nextInt();
for(int j = i;j > 0;j--){ //使用冒泡排序，对新插入的元素插入队列
if(map[j].dis < map[j-1].dis){
int index = map[j].index;
int pres = map[j].pre;
int dis = map[j].dis;
map[j].index = map[j-1].index;
map[j].pre = map[j-1].pre;
map[j].dis = map[j-1].dis;
map[j-1].index = index;
map[j-1].pre = pres;
map[j-1].dis = dis;
}else
break; //队列已经有序了，跳出循环
}
}
int Point[][] = new int[n+1][2]; //所有点的集合为图集，Point[i][0]表示点是否进入，Point[i][1]表示点所属类别
int max_dis = 0; //记录最大距离
int sum_point = 0; //记录有多少点进入了图集
int EquNum = 0; //标记等价类的个数
int mst[] = new int[n]; //标记进入图集的点的分类
int flag = 0; //记录已有进入的多少类了，合并之后不删除
for(int i = 0;i < m;i++){
if(sum_point == n && EquNum == 1)
break; //所有点都进入了点集，并且所有点都属于同一类了
if(Point[map[i].index][0] == 0 && Point[map[i].pre][0] == 0 ){//这两个点都没在图集中，
flag++;
EquNum++;
Point[map[i].index][1] = flag;
Point[map[i].pre][1] = flag;
mst[flag] = flag;
Point[map[i].index][0] = 1;
Point[map[i].pre][0] = 1;
max_dis = map[i].dis;
sum_point++;
sum_point++;
}else if(Point[map[i].pre][0] == 0 && Point[map[i].index][0] == 1){
Point[map[i].pre][0] = 1;
Point[map[i].pre][1] = Point[map[i].index][1];
max_dis = map[i].dis;
sum_point++;
}else if(Point[map[i].pre][0] == 1 && Point[map[i].index][0] == 0){
Point[map[i].index][0] = 1;
Point[map[i].index][1] = Point[map[i].pre][1];
max_dis = map[i].dis;
sum_point++;
}else{
if(mst[Point[map[i].index][1]] != mst[Point[map[i].pre][1]]){
max_dis = map[i].dis;
if(mst[Point[map[i].index][1]] > mst[Point[map[i].pre][1]]){
mst[Point[map[i].index][1]] = mst[Point[map[i].pre][1]];
}else
mst[Point[map[i].pre][1]] = mst[Point[map[i].index][1]];
EquNum--;
}
}
}
System.out.println(max_dis);
}
}
答案错误:您提交的程序没有通过所有的测试用例
case通过率为50.00%
测试用例:
4386 7121
1800 51 82
402 98 24
602 4049 100
341 3043 79
742 1692 40
3933 449 3
142 2747 3
2213 1905 73
4027 751 80
3398 3971 11
2813 1577 69
826 2150 35
3053 935 54
2043 585 39
31 3348 44
3355 1642 31
3120 2574 58
854 1803 39
1202 229 76
1944 1746 15
4034 3972 93
1327 3872 45
1363 2429 38
3042 1545 55
2770 3058 64
1055 2333 74
4357 1929 25
240 1167 45
case通过率为50.00%
测试用例:
4386 7121
1800 51 82
402 98 24
602 4049 100
341 3043 79
742 1692 40
3933 449 3
142 2747 3
2213 1905 73
4027 751 80
3398 3971 11
2813 1577 69
826 2150 35
3053 935 54
2043 585 39
31 3348 44
3355 1642 31
3120 2574 58
854 1803 39
1202 229 76
1944 1746 15
4034 3972 93
1327 3872 45
1363 2429 38
3042 1545 55
2770 3058 64
1055 2333 74
4357 1929 25
240 1167 45
。。。。
我是用的Kruskal算法来实现的，各位大神帮忙看看，这个测试用例没有过，但是个人感觉我的逻辑应该是没有错的，求解答
编辑于 2016-05-21 12:27:27
回复(1)
import java.util.*;
// 最小生成树：Kruskal
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), m = in.nextInt();
int[][] edge = new int[m][3];
for (int i = 0; i < m; i++) {
int p = in.nextInt() - 1, q = in.nextInt() - 1, k = in.nextInt();
edge[i][0] = p;
edge[i][1] = q;
edge[i][2] = k;
}
Arrays.sort(edge, (e1, e2)->e1[2] - e2[2]); // 边长 升序
int max = 0;
UnionFind uf = new UnionFind(n);
for (int[] e : edge) {
int p = e[0], q = e[1], k = e[2];
if (uf.union(p, q)) {
max = Math.max(max, k);
}
}
System.out.println(max);
}
}
// 并查集
class UnionFind {
int[] parent;
int[] rank;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 1;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public boolean union(int x, int y) {
int rootX = find(x), rootY = find(y);
if (rootX == rootY) return false;
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true;
}
}
发表于 2025-07-02 08:18:28
回复(0)
使用Kruskal最小生成树算法，双100%
import java.util.*;
class Edge implements Comparable{
int node1;
int node2;
int value;
public Edge(int node1, int node2, int value){
this.node1 = node1;
this.node2 = node2;
this.value = value;
}
public int compareTo(Object o){
Edge edge = (Edge)o;
if(this.value > edge.value)
return 1;
else if(this.value < edge.value)
return -1;
else
return 0;
}
}
class Solution{
int n;
int m;
int[] parent;
Edge[] edges;
// 并查集找到父节点
public int find(int x){
if(parent[x] != x){
parent[x] = find(parent[x]);
}
return parent[x];
}
public void run(){
Scanner reader = new Scanner(System.in);
while(reader.hasNext()){
n = reader.nextInt();
m = reader.nextInt();
if(n == 1)
System.out.println(0);
// 并查集初始化 父节点
parent = new int[n + 1];
for(int i = 1; i <= n; i++){
parent[i] = i;
}
// 初始化所有edge
edges = new Edge[m];
for(int i = 0; i < m; i++){
edges[i] = new Edge(reader.nextInt(), reader.nextInt(), reader.nextInt());
}
Arrays.sort(edges);
// 一条边一条边判断
int cntNode = 0;
for(int i = 0; i < m; i++){
Edge cur = edges[i];
int node1 = cur.node1;
int node2 = cur.node2;
int node1Parent = find(node1);
int node2Parent = find(node2);
// 每次选择不属于同一棵树的edge
if(parent[node1] != parent[node2]){
parent[node1Parent] = node2Parent;
cntNode++;
}
if(cntNode == n-1){
System.out.println(cur.value);
return;
}
}
}
}
}
public class Main{
public static void main(String[] args){
Solution solution = new Solution();
solution.run();
}
}
发表于 2021-03-15 15:17:51
回复(0)
#include<bits/stdc++.h>
using namespace std;
struct node{
int u,v;
int weight;
node(int u_,int v_,int w){
u = u_;v=v_;weight=w;
}
node(){}
};
vector<int>fa;
map<int,int>rank_;
int find(int x)
{
while(x!=fa[x])
x = fa[x];
return x;
}
bool union_(int x,int y)
{
int fa_x = find(x);
int fa_y = find(y);
if(fa_x!=fa_y)
{
int big = rank_[fa_x] > rank_[fa_y] ? fa_x : fa_y;
int small = big==fa_x ? fa_y : fa_x;
fa[small] = big;
rank_[big] += rank_[small];
rank_.erase(small);
return true;
}
return false;
}
bool cmp(node& a,node& b)
{
return a.weight<b.weight;
}
int main()
{
// 任何一块空地都要可达 就是得求一个连通块
// 连通块里最长的那条边尽可能小 即最小生成树
// kruskal
int n,m;
while(cin>>n>>m)
{
fa.resize(n+1);
for(int i=1;i<=n;++i)
{
fa[i] = i;
rank_[i] = 1;
}
vector<node>v;
for(int i=0;i<m;++i)
{
int a,b,c;
cin>>a>>b>>c;
v.push_back(node(a,b,c));
}
//cout<<v.size()<<endl;
sort(v.begin(),v.end(),cmp);
int k = 0;
int Max = 0;
//for(auto t:v)
// cout<<t.u<<t.v<<t.weight<<endl;
for(int i=0;i<v.size();++i)
{
if(union_(v[i].u,v[i].v))
{
Max = max(Max,v[i].weight);
++k;
}
if(k==n-1)
break;
}
cout<<Max<<endl;
}
return 0;
}
发表于 2020-04-18 15:44:42
回复(0)
#问题转化成求图的最小生成树，输出最小生成树里权值最大的边，Kruskal算法 import collections def find(x):#并查集 while x!=uni[x]: x=uni[x] return x N,M=list(map(int,input().split())) land=[list(map(int,input().split())) for i in range(M)] land=sorted(land,key=lambda x:x[2]) uni=list(range(N+1)) count=0 for line in land: s,e,v=line#起点，终点，权值 if s>e: s,e=e,s s=find(s) e=find(e) if s==e: continue else: uni[e]=s count+=1 if count==N-1: print(v) break
发表于 2018-10-01 16:36:32
回复(0)
暴力版的PRIM算法超时，只能过50%，所以用了简化版的并查集+Kruskal算法
Python代码如下
try:
def findx(x):
while x != uni[x]:
x = uni[x]
return x
while 1:
import collections
N,M = [int(x) for x in input().split()]
m_list = []
for i in range(M):
temp = [int(x) for x in input().split()]
m_list.append(temp)
uni = [i for i in range(N+1)]
m_list = sorted(m_list,key=lambda x:x[2])
v_count = 0
for line in m_list:
s,e,v = line
if s>e:
s,e = e,s
set_s = findx(s)
set_e = findx(e)
if set_e==set_s:
continue
else:
uni[set_e] = set_s
v_count+=1
if v_count==N-1:
print(v)
break
except EOFError:
pass
发表于 2018-07-04 14:10:01
回复(0)
#include <iostream>
#include <algorithm>
usingnamespacestd;
structE{
intP;
intQ;
intK;
};
boolcmp(E a,E b){//按照K排序。
returna.K<b.K;
}
intmain(){
intN,M;
cin>>N>>M;
structE road[M];
for(inti=0;i<M;i++){
cin>>road[i].P>>road[i].Q>>road[i].K;
}
sort(road,road+M,cmp);//排序
intmax_k=0;
intrr[N+1];
intcont=0;
for(inti=0;i<=N;i++){
rr[i]=0;
}
for(inti=0;i<M;i++){
intp=road[i].P;
intq=road[i].Q;
intk=road[i].K;
// cont++;
if(rr[p]==0&&rr[q]==0){//两个都为0；
rr[p]=p;
rr[q]=p;
max_k=max(max_k,k);
cont++;
}
elseif(rr[p]==0&&rr[q]!=0){//0 root
rr[p]=rr[q];
max_k=max(max_k,k);
}
elseif(rr[p]!=0&&rr[q]==0){//root 0
rr[q]=rr[p];
max_k=max(max_k,k);
cont++;
}
elseif(rr[p]==rr[q]&&rr[q]!=0){//同根
//不做任何处理
}
else{ //不同根
if(cont==(N-1)){ //退出条件
break;
}
else{//不退出时 root root 不同根
inttemp=rr[q];
rr[q]=rr[p];
max_k=max(max_k,k);
cont++;
for(intj=1;j<=N;j++){
if(rr[j]==temp){
rr[j]=rr[p];
}
}
}
}
}
cout<<max_k;
}
发表于 2018-04-15 23:32:25
回复(0)
题目说的是有n个空地，每个空地之间需要用一定长度的木材连接，求需要木材长度最少的方案。n个空地和空地间的木材构成一个图，求图的最小生成树即可。题目有一点没说清楚，它要求耗费木材最少，我想是的耗费的木材根数最少，结果一直认为要求最少边的生成树，然后就遍历导致超时了。
更多牛客网题解代码在https://github.com/ReyzalX/nowcoder查看。
#include<bits/stdc++.h>
usingnamespacestd;
structArc
{
intb, e;
intcost;
};
intmain()
{
//求最小生成树即可
intN, M;
cin >> N >> M;
vector<Arc> data(M);
//树的集合
vector<vector<int>> tree(N);
for(inti = 0; i < M; i++)
{
cin >> data[i].b >> data[i].e >> data[i].cost;
}
for(inti = 0; i < N; i++)
{
tree[i].push_back(i + 1);
}
sort(data.begin(), data.end(), [](Arc& c1, Arc& c2) {returnc1.cost < c2.cost; });
intlongestWood = 0;
for(inti = 0; i < M; i++)
{
intb = data[i].b;
inte = data[i].e;
intbIndex = -1;
inteIndex = -1;
for(inti = 0; i < N; i++)
{
if(find(tree[i].begin(),tree[i].end(),b) != tree[i].end())
{
bIndex = i;
}
if(find(tree[i].begin(), tree[i].end(), e) != tree[i].end())
{
eIndex = i;
}
}
if(bIndex == eIndex)
{
//已经在同一个集合中
continue;
}
tree[bIndex].insert(tree[bIndex].end(), tree[eIndex].begin(), tree[eIndex].end());
tree[eIndex].clear();
longestWood = max(longestWood, data[i].cost);
}
cout << longestWood << endl;
return0;
}
发表于 2018-03-26 10:11:13
回复(0)
哪位大神帮我看看我的哪里错了！！！！！！！！！！拜托拜托！！！！！！！
import java.util.Scanner;
/**
* 最小生成树知识点
* @author yg
*
*/
public class LongMood {
/**输入描述：第一行包含两个整数N(1≤N≤10000),M(1≤M≤1000000)。N表示公有N块空地。
* 接下来M行，每行包含三个整数P(1≤P≤N),Q(1≤Q≤N),K代表P,Q两个间没有鳄鱼，需要耗费K的木材。
*输出描述：一个整数，即耗费木材最少的情况下，最长的那根木材长度
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int max=0;
int min=0;
System.out.println("请输入空地N和行数M的值：");
Scanner input = new Scanner(System.in);
int n=input.nextInt();
int m=input.nextInt();
int [][]arr=new int[m][3];
System.out.println("输入各个元素：");
for(int i=0;i<m;i++){
for(int j=0;j<3;j++){
arr[i][j]=input.nextInt();
}
}
// for(int j=0;j<3;j++){
for(int i=0;i<m-1;i++){
min=i;//每轮查找最小数的下标
for(int h=i+1;h<m;h++){
if(arr[min][2]>arr[h][2]){
min=h;//保存最小数的下标
}
}
if(i!=min){
int temp0 = arr[i][0];
arr[i][0]=arr[min][0];
arr[min][0]=temp0;
int temp1 = arr[i][1];
arr[i][1]=arr[min][1];
arr[min][1]=temp1;
int temp2 = arr[i][2];
arr[i][2]=arr[min][2];
arr[min][2]=temp2;
}
}
// }
StringBuffer sbu=new StringBuffer();
for(int i=0;i<m;i++){
for(int j=0;j<2;j++){
String str=Integer.toString(arr[i][j]);
if(sbu.indexOf(str)<0){
sbu.append(str);
if(sbu.length()==n){
System.out.println(arr[i][2]);
break;
}
}
}
}
System.out.println(sbu);
/* for(int i=0;i<m;i++){
for(int j=0;j<3;j++){
System.out.print(arr[i][j]+" ");
}
System.out.println();
}*/
//1 2 8 1 6 7 1 5 5 2 6 2 2 3 1 3 6 4 3 4 3 4 6 2 4 5 1 5 6 4
}
}
发表于 2018-03-21 21:47:10
回复(0)
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct Node
{
int p;
int q;
int k;
}node;
vector<int> pre;
int unionsearch(int index) {
while (pre[index] != index) {
pre[index] = pre[pre[index]];
index = pre[index];
}
return index;
}
void join(int x, int y) {
if (pre[x] != pre[y]) {
pre[x] = y;
}
}
bool cmp(const node& vn1, const node & vn2) {
return vn1.k < vn2.k;
}
int main(void) {
int N, M;
scanf("%d %d", &N, &M);
vector<node> vn;
for (int i = 0; i < M; i++) {
node tmp;
scanf("%d %d %d", &tmp.p, &tmp.q, &tmp.k);
vn.push_back(tmp);
}
// initialize union set;
for (int i = 0; i <= N; i++) {
pre.push_back(i);
}
sort(vn.begin(), vn.end(), cmp);
int res = 0;
for (int i = 0; i < M; i++) {
int rootA = unionsearch(vn[i].p);
int rootB = unionsearch(vn[i].q);
if (rootA != rootB) {
if (res < vn[i].k) {
res = vn[i].k;
}
join(rootA, rootB);
}
}
cout << res << endl;
return 0;
}
发表于 2018-03-15 14:34:56
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
