并查集-城市建设

亦凉 2022-07-12 12:14 141阅读 0赞

package 搜索.并查集;  
import java.util.Arrays;  
import java.util.Comparator;  
import java.util.Scanner;  
  
  
public class 城市建设 \{  
static class Edge \{  
public int to;  
public int next;  
public int price;  
  
  
public Edge(int to, int next, int price) \{  
super();  
this.to = to;  
this.next = next;  
this.price = price;  
\}  
  
  
\}  
  
  
static Edge\[\] edge;  
static int\[\] pre;  
static int n;  
  
  
public static void main(String\[\] args) \{  
Scanner sc = new Scanner(System.in);  
n = sc.nextInt();  
int m = sc.nextInt();  
edge = new Edge\[m + n\];  
pre = new int\[n + 1\];  
for (int i = 0; i < m; i++) \{  
edge\[i\] = new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt());  
\}  
int count = 0;  
  
  
for (int i = 1; i <= n; i++) \{  
int price = sc.nextInt();  
if (price != -1) \{  
edge\[m + count\] = new Edge(0, i, price);  
count++;  
\}  
\}  
int result1 = dfs(n, m);  
int result2 = dfs(n + 1, m + count);  
if (result1 != -1) \{  
result2 = Math.min(result1, result2);  
\}  
System.out.println(result2);  
  
  
\}  
  
  
private static int dfs(int n, int m) \{  
init(m);  
int maxPrice = 0;  
int count = 0;  
for (int i = 0; i < m; i++) \{  
if (union(edge\[i\].to, edge\[i\].next)) \{  
maxPrice += (edge\[i\].price);  
count++;  
\} else if (edge\[i\].price < 0) \{  
maxPrice -= 1;  
\}  
\}  
if (count != n - 1)  
return -1;  
return maxPrice;  
\}  
  
  
private static void init(int m) \{  
for (int i = 0; i <= n; i++)  
pre\[i\] = i;  
Arrays.sort(edge, 0, m, new Comparator<Edge>() \{  
public int compare(Edge o1, Edge o2) \{  
return o1.price - o2.price;  
\}  
\});  
\}  
  
  
private static boolean union(int to, int next) \{  
int x = find(to);  
int y = find(next);  
if (x != y) \{  
pre\[x\] = pre\[y\];  
return true;  
\}  
return false;  
\}  
  
  
private static int find(int to) \{  
  
  
int root = to;  
while (root != pre\[root\]) \{  
root = pre\[root\];  
\}  
int temp;  
while (to != root) \{  
temp = pre\[to\];  
pre\[to\] = root;  
to = temp;  
\}  
return root;  
\}  
\}

发表评论取消回复

表情：

评论列表（有 0 条评论，141人围观）

还没有评论，来说两句吧...

相关阅读

相关并查集 Ⅱ

\[poj 1611\] ([http://poj.org/problem?id=1611][http_poj.org_problem_id_1611]) 题目描述： T

古城微笑少年丶/ 2022年08月03日 14:35/ 0 赞/ 279 阅读

相关并查集-城市建设

package 搜索.并查集; import java.util.Arrays; import java.util.Comparator; import java.

亦凉/ 2022年07月12日 12:14/ 0 赞/ 142 阅读

相关并查集

并查集JAVA版框架并查集是一种用来管理元素分组情况的数据结构。并查集可以高效地进行如下操作： \--查询元素a和元素b是否属于同一组

落日映苍穹つ/ 2022年06月16日 12:44/ 0 赞/ 315 阅读

相关并查集

这个文章是几年前水acm的时候转的, 当时也不知道作者是谁, 要是有人知道的话说一下吧并查集是我暑假从高手那里学到的一招，觉得真是太精妙的设计了。以前我无法解决的

港控/mmm°/ 2022年06月13日 14:13/ 0 赞/ 301 阅读

相关并查集

> 题目 > 某学校近期要组织全校同学出去参加某项活动，由于人数众多，学校决定让同学们自行组队，以小组为单位进行活动。假设学校一共n个同学，每个同学有一个唯一的数字作为标签

Myth丶恋晨/ 2022年06月08日 09:24/ 0 赞/ 308 阅读

相关并查集

森林: 森林是由若干棵互不相交的树组成,两棵树分别独立,没有交集 ![20181112082744488.png][] 并查集: 并查集的结构和森林十分相似,是

Love The Way You Lie/ 2022年04月17日 02:27/ 0 赞/ 367 阅读

相关并查集

来看一个实例，[杭电1232畅通工程][1232] 首先在地图上给你若干个城镇，这些城镇都可以看作点，然后告诉你哪些对城镇之间是有道路直接相连的。最后要解决的是整幅图的连通性

我就是我/ 2022年03月29日 10:58/ 0 赞/ 371 阅读

相关并查集

例题： ![输入样例][20190805122001677.png] 输入样例，第一行为一个整数n，代表有n台电脑，编号1-n；接下来进行一系列操作，当输入‘c’时，判

Dear 丶/ 2021年11月11日 08:04/ 0 赞/ 388 阅读

相关并查集

一、算法解释用于解决一些有N个元素的集合应用问题。 1、将每个元素初始化为自身单独成为一个集合。用p\[i\]的值表示该元素所在集合。 ![这里写图片描述][S

桃扇骨/ 2021年09月14日 02:56/ 0 赞/ 475 阅读

相关并查集

并查集的作用就是快速判断两个元素是否在同一个集合中，快速将两个集合合并基本模板 include <iostream> include <a

比眉伴天荒/ 2021年06月22日 15:37/ 0 赞/ 573 阅读