藍橋杯2020年真題:網路分析

題目

時間限制: 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);
			}
		}
	}
}