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];
  }
}