比赛刷题总结

1. 图论题目

1.1 网红点打卡攻略

题目链接

// 代码如下：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
/**
 * 假设你从家里出发，从 V1 开始打卡，最后从 Vn 回家
 */
public class Main {
    final static int INF = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] split = in.readLine().split(" ");
        int n = Integer.parseInt(split[0]);
        int m = Integer.parseInt(split[1]);
        int[][] g = new int[n+1][n+1];
        boolean[] vis = new boolean[n + 1]; // 标志是否访问过该点
        // 初始不同到达的地方为最大值
        for (int i = 0; i <= n; i++) {
            Arrays.fill(g[i] , INF);
        }
        for (int i = 0; i < m; i++) {
            String[] split1 = in.readLine().split(" ");
            int start = Integer.parseInt(split1[0]);
            int end = Integer.parseInt(split1[1]);
            int cost = Integer.parseInt(split1[2]);
            g[start][end] = cost;
            g[end][start] = cost;
        }
        int k = Integer.parseInt(in.readLine());
        int count = 0  , res = Integer.MAX_VALUE  , mId = 0;
        for (int i = 1; i <= k; i++) {         // 一共有k个路线来需要进行 判断哦
            int cnt = 0;
            int sum = 0;
            vis = new boolean[n+1]; // 保证每一个网红点之访问一次
            split = in.readLine().split(" ");
            // 表示这条路线一共n个网红点
            m = Integer.parseInt(split[0]);

            int[] ints = new int[m];
            for (int j = 0; j < m; j++) {
                ints[j] = Integer.parseInt(split[j+1]);
            }
            if (g[0][ints[0]] != INF){
                sum += g[0][ints[0]];
            }else {
                // 表示走不通，直接结束本次循环，判断一条路线
                continue;
            }
            int j ;
            for (j = 0; j < m - 1; j++) {
                if (g[ints[j]][ints[j+1]] != INF && !vis[ints[j]]){
                    sum += g[ints[j]][ints[j+1]];
                    // 将当前节点标记为：访问过了
                    vis[ints[j]] = true;
                    // 记录走过的网红点数量
                    cnt++;
                }else {
                    break;
                }
            }
            if (j != m - 1){
                // 表示非正常退出，中间走不通
                continue;
            }
            if (g[ints[m - 1]][0] != INF && !vis[ints[m-1]] ){
                // 表示也可以从当前的最后一个景点到达回家中
                sum += g[ints[m - 1]][0];
                vis[ints[m - 1]] = true;
                cnt++;
            }else {
                continue;
            }
            if (cnt != n){
                // 此时一共n个点，如果返回的景点数量不是n，则返回，不正确
                continue;
            }
            //走到这个地方表示满足了条件
            count++;
            if (sum < res){
                res = sum;
                mId = i;
            }
        }
        System.out.println(count);
        System.out.println(mId+" "+res);
    }
}

1.2 记忆化搜索

题目 相关博文1

// 代码如下
public class Main{
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static List<List<Integer>> g = new ArrayList<>();
    static boolean[] vis = new boolean[501]; // 坚决不浪费一点空间
    static int[] step ;
    static boolean flag = false;
    static int a , b , u , v , n , m ;
    public static void main(String[] args) throws IOException {
        String[] split = in.readLine().split(" ");
        n = Integer.parseInt(split[0]);
        m = Integer.parseInt(split[1]);
        step = new int[n+1]; //  step[i] : 用来表示 从i到目标节点的路径个数
        // 初始化g
        for (int i = 0; i <= n; i++) {
            g.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            split = in.readLine().split(" ");
            u = Integer.parseInt(split[0]);
            v = Integer.parseInt(split[1]);
            // 构建链接 ： 表示从u出发，下一步可以到达的地方，构成一个list存储
            g.get(u).add(v);
        }
        split = in.readLine().split(" ");
        a = Integer.parseInt(split[0]);
        b = Integer.parseInt(split[1]);
        Arrays.fill(step , 0);
        step[b] = 1;
        vis[b] = true;
        // 然后开始从a出发，计算到达b的路劲个数
        dfs(a);
        System.out.print(step[a]);
        if (flag){
            System.out.println(" No");
        }else {
            System.out.println(" Yes");
        }
    }
    private static void dfs(int cur) {
        vis[cur] = true;
        if (g.get(cur).size() == 0 && cur != b){
            flag = true;
            return;
        }
        for (int next : g.get(cur)) {
            // 然后判断下一个是不是可以访问到
            if (!vis[next]){
                // 表示下一个没有访问过，可以进行访问哦
                dfs(next);
            }
            // 本次结束之后，然后计算
            step[cur] += step[next];
        }
    }
}