2020蓝桥杯Java B组省赛 网络分析 思路 代码 注释

10.网络分析

问题描述

小明正在做一个网络实验。

他设置了 n 台电脑，称为节点，用于收发和存储数据。

初始时，所有节点都是独立的，不存在任何连接。

小明可以通过网线将两个节点连接起来，连接后两个节点就可以互相通信

了。两个节点如果存在网线连接，称为相邻。

小明有时会测试当时的网络，他会在某个节点发送一条信息，信息会发送

到每个相邻的节点，之后这些节点又会转发到自己相邻的节点，直到所有直接

或间接相邻的节点都收到了信息。所有发送和接收的节点都会将信息存储下来。

一条信息只存储一次。

给出小明连接和测试的过程，请计算出每个节点存储信息的大小。

输入格式

输入的第一行包含两个整数 n, m，分别表示节点数量和操作数量。节点从

1 至 n 编号。

接下来 m 行，每行三个整数，表示一个操作。

如果操作为 1 a b，表示将节点 a 和节点 b 通过网线连接起来。当 a = b

时，表示连接了一个自环，对网络没有实质影响。

如果操作为 2 p t，表示在节点 p 上发送一条大小为 t 的信息。

输出格式

输出一行，包含 n 个整数，相邻整数之间用一个空格分割，依次表示进行

完上述操作后节点 1 至节点 n 上存储信息的大小。

测试样例1

Input：

4 8

1 1 2

2 1 10

2 3 5

1 4 1

2 2 2

1 1 2

1 2 4

2 2 1Output：

13 13 5 3

1

2

3

4

5

6

7

8

9

10

11

12

13

评测用例规模与约定

思路

• 使用带权并查集进行 查 与 合并 操作
• 按题意要求 需要记录补偿数据 目的是即使两个集合相连 也可以通过补偿值来找回相连前各自的数值 才满足题意

import java.util.Scanner;
import java.util.function.IntPredicate;

public class Main{
  //存储该节点接收的数据大小
  static int[] value;
  //存储该节点连接的节点
  static int[] parent;
  //存储该节点在因为其他节点进行连接操作后数据补偿数值
  static int[] compensation;
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int m = scanner.nextInt();
    value = new int[n + 1];
    parent = new int[n + 1];
    compensation = new int[n + 1];
    //初始情况无连接
    for(int i = 1; i <= n; i++)parent[i] = i;
    for(int i = 0; i < m; i++) {
      int type = scanner.nextInt();
      int a = scanner.nextInt();
      int b = scanner.nextInt();
      if(type == 1) {
        //找到两个节点的根节点进行合并
        a = find(a);
        b = find(b);
        if(a != b) {
          //连接
          parent[a] = b;
          //记录补偿 补偿的原因是这些数据是在连接前发送的 不能计入自身数据
          compensation[a] = value[a] - value[b]; 
        }
      }else {
        //根节点数据变化即可
        value[find(a)] += b;
      }
    }
    //根节点数值加上补偿数值才是真正接收到的数据大小
    for(int i = 1; i <= n; i++)System.out.printf((value[find(i)] + compensation[i])+" ");
  }
  public static int find(int x) {
    if(x != parent[x]) {
      int temp = parent[x];
      parent[x] = find(parent[x]);
      //叠加补偿 否则连接后的数据有误 可以想象连接两到三次的情形
      compensation[x] += compensation[temp];
    }
    return parent[x];
  }
}