117.软件构建
思路:看了一下蓝不过海呀的视频,要找到入度为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; // 起始点到自身的距离为0
for (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();
}
}
小结
dijkstra三部曲:
- 第一步,选源点到哪个节点近且该节点未被访问过
- 第二步,该最近节点被标记访问过
- 第三步,更新非访问节点到源点的距离(即更新minDist数组)
minDist数组 用来记录 每一个节点距离源点的最小距离