当前位置:   article > 正文

代码随想录Day72(图论Part08)

代码随想录Day72(图论Part08)

117.软件构建

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

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

尝试(有思路,对数据结构不了解,写不出来)
  1. import java.util.*;
  2. class Main{
  3. public static int n;
  4. public static int m;
  5. public static void main(String[] args){
  6. Scanner scanner = new Scanner(System.in);
  7. n = scanner.nextInt();
  8. m = scanner.nextInt();
  9. int[][] grid = new int[m][2];
  10. for(int i=0; i<m; i++){
  11. int s = scanner.nextInt();
  12. int t = scanner.nextInt();
  13. grid[i] =
  14. }
  15. for(){
  16. //遍历map,从1-5,找不到的value,说明入度为0
  17. //删掉该点和该点的出度
  18. //将该点加入到结果数组中
  19. }
  20. // 遍历输出数组
  21. }
  22. }
答案
  1. import java.util.*;
  2. class Main{
  3. public static void main(String[] args){
  4. Scanner sc = new Scanner(System.in);
  5. int n = sc.nextInt();
  6. int m = sc.nextInt();
  7. int[] in_degree = new int[n];
  8. Map<Integer, ArrayList<Integer>> map = new HashMap<>();
  9. ArrayList<Integer> res= new ArrayList<>();
  10. for(int i=0;i<m;i++){
  11. int s = sc.nextInt();
  12. int t = sc.nextInt();
  13. in_degree[t] ++;
  14. ArrayList<Integer> list = new ArrayList<>();
  15. if (!map.containsKey(s)){
  16. list.add(t);
  17. }else{
  18. list = map.get(s);
  19. list.add(t);
  20. }
  21. map.put(s, list);
  22. }
  23. Queue<Integer> queue = new LinkedList<>();
  24. for(int i =0;i<n;i++){
  25. if(in_degree[i] == 0) queue.offer(i);
  26. }
  27. while (!queue.isEmpty()){
  28. int cur = queue.peek();
  29. queue.poll();
  30. res.add(cur);
  31. if(map.containsKey(cur)){
  32. ArrayList<Integer> files = map.get(cur);
  33. if(!files.isEmpty()){
  34. for(int i = 0;i<files.size();i++){
  35. in_degree[files.get(i)]--;
  36. if (in_degree[files.get(i)]==0) queue.offer(files.get(i));
  37. }
  38. }
  39. }
  40. }
  41. if(res.size() == n){
  42. for (int i = 0;i<n-1;i++){
  43. System.out.print(res.get(i) + " ");
  44. }
  45. System.out.print(res.get(res.size()-1) );
  46. }else{
  47. System.out.print(-1);
  48. }
  49. }
  50. }
小结

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

47.参加科学大会

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

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

答案
  1. import java.util.*;
  2. public class Main {
  3. public static void main(String[] args) {
  4. Scanner scanner = new Scanner(System.in);
  5. int n = scanner.nextInt(); // 顶点数
  6. int m = scanner.nextInt(); // 边数
  7. int[][] grid = new int[n + 1][n + 1];
  8. for (int i = 1; i <= n; i++) {
  9. Arrays.fill(grid[i], Integer.MAX_VALUE);
  10. }
  11. for (int i = 0; i < m; i++) {
  12. int p1 = scanner.nextInt();
  13. int p2 = scanner.nextInt();
  14. int val = scanner.nextInt();
  15. grid[p1][p2] = val;
  16. }
  17. int start = 1;
  18. int end = n;
  19. // 存储从源点到每个节点的最短距离
  20. int[] minDist = new int[n + 1];
  21. Arrays.fill(minDist, Integer.MAX_VALUE);
  22. // 记录顶点是否被访问过
  23. boolean[] visited = new boolean[n + 1];
  24. minDist[start] = 0; // 起始点到自身的距离为0
  25. for (int i = 1; i <= n; i++) { // 遍历所有节点
  26. int minVal = Integer.MAX_VALUE;
  27. int cur = 1;
  28. // 1、选距离源点最近且未访问过的节点
  29. for (int v = 1; v <= n; ++v) {
  30. if (!visited[v] && minDist[v] < minVal) {
  31. minVal = minDist[v];
  32. cur = v;
  33. }
  34. }
  35. visited[cur] = true; // 2、标记该节点已被访问
  36. // 3、第三步,更新非访问节点到源点的距离(即更新minDist数组)
  37. for (int v = 1; v <= n; v++) {
  38. if (!visited[v] && grid[cur][v] != Integer.MAX_VALUE && minDist[cur] + grid[cur][v] < minDist[v]) {
  39. minDist[v] = minDist[cur] + grid[cur][v];
  40. }
  41. }
  42. }
  43. if (minDist[end] == Integer.MAX_VALUE) {
  44. System.out.println(-1); // 不能到达终点
  45. } else {
  46. System.out.println(minDist[end]); // 到达终点最短路径
  47. }
  48. scanner.close();
  49. }
  50. }
小结

 dijkstra三部曲

  1. 第一步,选源点到哪个节点近且该节点未被访问过
  2. 第二步,该最近节点被标记访问过
  3. 第三步,更新非访问节点到源点的距离(即更新minDist数组)

minDist数组 用来记录 每一个节点距离源点的最小距离

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/寸_铁/article/detail/804933
推荐阅读
相关标签
  

闽ICP备14008679号