時間限制: 1.0s 記憶體限制: 512.0MB 本題總分：25 分
【問題描述】
小明正在做一個網路實驗。 他設定了 n 臺電腦，稱為節點，用於收發和儲存資料。
初始時，所有節點都是獨立的，不存在任何連線。
小明可以通過網線將兩個節點連線起來，連線後兩個節點就可以互相通訊了。
兩個節點如果存在網線連線，稱為相鄰。
小明有時會測試當時的網路，他會在某個節點傳送一條資訊，
資訊會傳送到每個相鄰的節點，之後這些節點又會轉發到自己相鄰的節點，
直到所有直接 或間接相鄰的節點都收到了資訊。
所有傳送和接收的節點都會將資訊儲存下來。 一條資訊只儲存一次。
給出小明連線和測試的過程，請計算出每個節點儲存資訊的大小。
【輸入格式】
輸入的第一行包含兩個整數 n,m，分別表示節點數量和運算元量。
節點從 1 至 n 編號。 接下來 m 行，每行三個整數，表示一個操作。
如果操作為 1 a b，表示將節點 a 和節點 b 通過網線連線起來。
當 a = b 時，表示連線了一個自環，對網路沒有實質影響。
如果操作為 2 p t，表示在節點 p 上傳送一條大小為 t 的資訊。
【輸出格式】
輸出一行，包含 n 個整數，相鄰整數之間用一個空格分割，
依次表示進行 完上述操作後節點 1 至節點 n 上儲存資訊的大小。
【樣例輸入】
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 1
【樣例輸出】
13 13 5 3
【評測用例規模與約定】
對於 30% 的評測用例，1≤n≤20，1≤m≤100。
對於 50% 的評測用例，1≤n≤100，1≤m≤1000。
對於 70% 的評測用例，1≤n≤1000，1≤m≤10000。
對於所有評測用例，1≤n≤10000，1≤m≤100000，1≤t≤100。
package competition4;
import java.util.Scanner;
/*
5 7
1 1 2
1 1 3
1 4 5
2 1 1
2 4 1
1 3 5
2 1 10
*/
public class NetworkProblem
{
/*
* 這裡我想的是使用類似Kruskal演演算法裡面的找一個節點的頂點的演演算法(類似並查集)
* 這裡也是想將它們弄成一棵樹,如果某個節點傳送了一條資料,
* 那麼誰會進行接受呢?這裡會將所有的節點的頂點和傳送資料的這個節點
* 的頂點相同的話,就全部儲存當前節點傳送的資料
* 但是後面我就發現它和最小生成樹有著本質的不一樣的需求,最小生成樹只要確保頂點是否是一樣就行
* 而它在傳送資料的時候因為不知道從哪裡開始,那麼就得需要知道每一個和它相連的節點
* 如果是找父節點還行,但是這裡還需要尋找所有的子節點,所以這裡的方法不可行,
* 比如上面的資料就不能通過
*/
public static int n,m;
public static void main(String[] args)
{
int[][] graph;
Scanner in = new Scanner(System.in);
n=in.nextInt();
m=in.nextInt();
//這裡2+1和n+1都是為了方便我自己運算元據
//其中一行用來儲存當前節點的頂點是誰,另外一行表示當前節點儲存的資料的大小
graph=new int[2+1][n+1];
int temp,start,end;
for(int x=1;x<=m;x++)
{
temp=in.nextInt();
start=in.nextInt();
end=in.nextInt();
if(temp==1)
{
if(graph[1][end]!=0)
{
graph[1][start]=graph[1][end];
}
else
{
graph[1][start]=end;
}
}
else
{
graph[2][start] +=end;
//如果它不是頂點:那麼它就是自己單獨的,要麼就是肯定有頂點
if(graph[1][start]!=0)
{
int index=graph[1][start];
//這裡需要注意一下,就因為題目的兩臺主機,如果網路已經連線好了
//後面可能還會繼續進行連線,那麼就會出現當前節點的頂點就是自己
if(index != start)
graph[2][index] +=end;
for(int y=1;y<=n;y++)
{
if(graph[1][y]==index && y!=start && y!=index)
{
graph[2][y] +=end;
}
}
}
//那麼現在它自己是頂點,將全部頂點是它的加上它傳送的資料大小
else
{
for(int y=1;y<=n;y++)
{
if(graph[1][y]==start && y!=start)
{
graph[2][y] +=end;
}
}
}
}
}
in.close();
//最後將每個節點的資料量大小輸出
for(int x=1;x<=n;x++)
{
System.out.print(graph[2][x]+" ");
}
}
}
改進
這裡採用的是並查集,但是應該只能通過70%的資料,
因為上面的測試用例中1≤n≤10000，1≤m≤100000，這裡演演算法複雜度是n*m
package competition4;
import java.util.HashSet;
import java.util.Scanner;
/*
5 7
1 1 2
1 1 3
1 4 5
2 1 1
2 4 1
1 3 5
2 1 10
*/
public class NetworkProblem3
{
public static int n,m;
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
n=in.nextInt();
m=in.nextInt();
//表示每個節點儲存的資料大小
int[] weight=new int[n+1];
int temp,start,end;
//初始化並查集工具
UF uf = new UF(n);
for(int x=1;x<=m;x++)
{
temp=in.nextInt();
start=in.nextInt();
end=in.nextInt();
if(temp==1)
{
if (uf.find(start) != uf.find(end))
{
uf.union(start,end);
}
}
else
{
int i = uf.find(start);
for(int z=1;z<uf.parent.length;z++)
{
if(uf.parent[z]==i)
{
weight[z] +=end;
}
}
}
}
for(int x=1;x<weight.length;x++)
{
System.out.print(weight[x]+" ");
}
}
private static class UF
{
int n;
int[] parent;
public UF(int n)
{
this.n = n;
parent = new int[n + 1];
for (int i = 1; i <= n; i++)
{
parent[i] = i;
}
}
//查詢哪一個節點,就會將和這個節點相連的所有節點的頂點都設定成當前頂點
int find(int x)
{
return parent[x]==x?x:parent[x];
}
//將某個節點加入到某個並集裡面,
//那麼也需要將這兩個節點本來所在的集合的全部節點的頂點都修改成同一個頂點
void union(int a, int b)
{
HashSet<Integer> path = new HashSet<>();
int end1=parent[a]==a?a:parent[a];
int end2=parent[b]==b?b:parent[b];
for(int x=1;x<parent.length;x++)
{
if(parent[x]==end1 || parent[x]==end2)
{
path.add(x);
}
}
for (Integer xx : path)
{
parent[xx] = end1;
}
parent[end2] = end1;
}
}
}
網上大佬的思路
我覺得這個寫得還是挺好的,裡面雖然進行深度的dfs
但是有bool陣列進行截枝,所以應該不會棧溢位的,應該也能通過所有測試樣例
package competition4;
import java.util.LinkedList;
import java.util.Scanner;
public class NetworkProblemOfOther2
{
static int[] data;
static boolean[] bool;
static LinkedList<LinkedList<Integer>> list = new LinkedList<LinkedList<Integer>>();
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
data = new int[n + 1];
bool = new boolean[n + 1];
int a = 0, b = 0, c = 0;
for (int i = 0; i <= n; i++)
{
list.add(new LinkedList<>());
}
for (int i = 0; i < m; i++)
{
a = sc.nextInt();
b = sc.nextInt();
c = sc.nextInt();
if (a == 1)
{
list.get(b).add(c);
list.get(c).add(b);
} else
{
bool = new boolean[n + 1];
dfs(b, c);
}
}
for (int i = 1; i <= n; i++)
{
System.out.print(data[i]+" ");
}
}
public static void dfs(int node, int num)
{
bool[node] = true;
data[node] += num;
LinkedList<Integer> templist = list.get(node);
for (int i : templist)
{
if (!bool[i])
{
dfs(i, num);
}
}
}
}