代码随想录Day72（图论Part08）

2024/10/25 21:27:59 来源：https://blog.csdn.net/Allen_7_kklt/article/details/140162426 浏览: 次关键词：代码随想录Day72（图论Part08）

117.软件构建

题目：117. 软件构建 (kamacoder.com)

思路：看了一下蓝不过海呀的视频，要找到入度为0的点，删掉该点和该点的出度，要用一个数据结构存起来边，而且要方便删除

尝试（有思路，对数据结构不了解，写不出来）

import java.util.*;class Main{public static int n;public static int m;public static void main(String[] args){Scanner scanner = new Scanner(System.in);n = scanner.nextInt();m = scanner.nextInt();int[][] grid = new int[m][2];for(int i=0; i<m; i++){int s = scanner.nextInt();int t = scanner.nextInt();grid[i] = }for(){//遍历map，从1-5，找不到的value，说明入度为0//删掉该点和该点的出度//将该点加入到结果数组中}// 遍历输出数组}
}

答案

import java.util.*;
class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[] in_degree = new int[n];Map<Integer, ArrayList<Integer>> map = new HashMap<>();ArrayList<Integer> res= new ArrayList<>();for(int i=0;i<m;i++){int s = sc.nextInt();int t = sc.nextInt();in_degree[t] ++;ArrayList<Integer> list = new ArrayList<>();if (!map.containsKey(s)){list.add(t);}else{list = map.get(s);list.add(t);}map.put(s, list);}Queue<Integer> queue = new LinkedList<>();for(int i =0;i<n;i++){if(in_degree[i] == 0) queue.offer(i);}while (!queue.isEmpty()){int cur = queue.peek();queue.poll();res.add(cur);if(map.containsKey(cur)){ArrayList<Integer> files = map.get(cur);if(!files.isEmpty()){for(int i = 0;i<files.size();i++){in_degree[files.get(i)]--;if (in_degree[files.get(i)]==0) queue.offer(files.get(i));}}}}if(res.size() == n){for (int i = 0;i<n-1;i++){System.out.print(res.get(i) + " ");}System.out.print(res.get(res.size()-1) );}else{System.out.print(-1);}}
}

小结

Map<Integer, ArrayList<Integer>> map = new HashMap<>();存储节点和节点依赖关系

47.参加科学大会

题目：47. 参加科学大会（第六期模拟笔试） (kamacoder.com)

思路：直接看的蓝不过海呀的视频，懒得自己写了，抄一遍

答案

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();  // 顶点数int m = scanner.nextInt();  // 边数int[][] grid = new int[n + 1][n + 1];for (int i = 1; i <= n; i++) {Arrays.fill(grid[i], Integer.MAX_VALUE);}for (int i = 0; i < m; i++) {int p1 = scanner.nextInt();int p2 = scanner.nextInt();int val = scanner.nextInt();grid[p1][p2] = val;}int start = 1;int end = n;// 存储从源点到每个节点的最短距离int[] minDist = new int[n + 1];Arrays.fill(minDist, Integer.MAX_VALUE);// 记录顶点是否被访问过boolean[] visited = new boolean[n + 1];minDist[start] = 0;  // 起始点到自身的距离为0for (int i = 1; i <= n; i++) { // 遍历所有节点int minVal = Integer.MAX_VALUE;int cur = 1;// 1、选距离源点最近且未访问过的节点for (int v = 1; v <= n; ++v) {if (!visited[v] && minDist[v] < minVal) {minVal = minDist[v];cur = v;}}visited[cur] = true;  // 2、标记该节点已被访问// 3、第三步，更新非访问节点到源点的距离（即更新minDist数组）for (int v = 1; v <= n; v++) {if (!visited[v] && grid[cur][v] != Integer.MAX_VALUE && minDist[cur] + grid[cur][v] < minDist[v]) {minDist[v] = minDist[cur] + grid[cur][v];}}}if (minDist[end] == Integer.MAX_VALUE) {System.out.println(-1); // 不能到达终点} else {System.out.println(minDist[end]); // 到达终点最短路径}scanner.close();}
}