题解 | #旅行Ⅰ#

题意整理

给定N个城市，以及每个城市的开销。
一个前置城市数组，去y城市之前必须先去x城市。
牛妹手上有V元，她每次都会去开销最小的城市，如果开销相同，就选编号较小的城市，求牛妹最多能去几个城市。

方法一（优先队列+拓扑排序）

1.解题思路

首先明确一个事实，如果要去某个城市，那么他的前置城市一定都去过了，否则去不了这个城市。于是只要前置城市数目为0，就可以尝试访问这个城市，我们假设前置城市数为入度，记录在对应的Indeg入度数组。

由于每次都要选择花费最小的城市，如果花费相同，则选择编号最小的城市，所以可以将待去城市加入到优先队列（优先队列存放城市开销和城市编号组成的长度为2的数组），每次取优先队列的最小值，即可满足上述选择策略。

明确思路后，先将入度为0的城市开销、编号添加到队列。
如果当前剩余花费V还够当前城市的开销，则减去对应的开销cost，同时可去城市数cnt加一。然后检查所去的这个城市的所有后置城市，将对应后置城市入度减一，如果入度变为0，则将对应城市、编号加入到队列。

动图展示：
图片说明

2.代码实现

import java.util.*;

/*
 * public class Point {
 *   int x;
 *   int y;
 *   public Point(int x, int y) {
 *     this.x = x;
 *     this.y = y;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param N int整型 N
     * @param V int整型 V
     * @param A int整型一维数组 A
     * @param list Point类一维数组 List
     * @return int整型
     */
    public int Travel (int N, int V, int[] A, Point[] list) {
        //初始化优先队列
        PriorityQueue<int[]> queue=new PriorityQueue<>(
              (o1,o2)->o1[0]==o2[0]?o1[1]-o2[1]:o1[0]-o2[0]);

        //初始化入度数组、后置城市数组
        int[] Indeg=new int[N];
        int[][] limit=new int[N][N];

        //给后置城市数组和入度数组赋值
        for(Point p:list){
            limit[p.x-1][p.y-1]=1;
            Indeg[p.y-1]++;
        }

        //如果入度为0，则表示可以访问，加入到队列
        for(int i=0;i<N;i++){
            if(Indeg[i]==0){
                queue.offer(new int[]{A[i],i});
            }
        }

        //记录最多可去城市数目
        int cnt=0;
        while(!queue.isEmpty()){
            int[] city=queue.poll();
            int cost=city[0];
            int id=city[1];
            //如果剩余花费不够，则直接跳出循环
            if(V<cost) break;
            V-=cost;
            cnt++;
            //如果存在后置城市，将对应后置城市入度减一
            for(int j=0;j<N;j++){
                if(limit[id][j]==1){
                    Indeg[j]--;
                    //如果入度为0，则加入到队列
                    if(Indeg[j]==0){
                        queue.offer(new int[]{A[j],j});
                    }
                }
            }
        }

        return cnt;

    }
}

3.复杂度分析

时间复杂度：由于每个城市最多访问一次，而从队列中添加或移除城市的时间复杂度都是 $O(log_2n)$ ，所以最终的时间复杂度是 $O(nlog_2n)$ 。
空间复杂度：需要额外大小为 $n^2$ 的limit数组，所以空间复杂度是 $O(n^2)$ 。

方法二（优先队列+标记数组）

1.解题思路

牛妹每次都要选择花费最小的城市，如果花费相同，则选择编号最小的城市，所以可以将待去城市加入到优先队列（优先队列存放城市开销和城市编号组成的长度为2的数组），每次取优先队列的最小值，即可满足上述选择策略。

首先初始化优先队列、入度数组、标记数组（用来判断某个城市是否来过）、后置城市数组，先将入度为0的城市开销、编号添加到队列，并将对应标记置为true。
每次取优先队列的最小值，如果当前花费还够，则减去对应开销，并将可去城市数cnt加一。然后将对应的后置数组里的所有城市入度减一。遍历所有的城市，如果没有访问过，并且入度为0，则加入到队列。

2.代码实现

import java.util.*;

/*
 * public class Point {
 *   int x;
 *   int y;
 *   public Point(int x, int y) {
 *     this.x = x;
 *     this.y = y;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param N int整型 N
     * @param V int整型 V
     * @param A int整型一维数组 A
     * @param list Point类一维数组 List
     * @return int整型
     */
    public int Travel (int N, int V, int[] A, Point[] list) {
        //初始化优先队列
        PriorityQueue<int[]> queue=new PriorityQueue<>(
              (o1,o2)->o1[0]==o2[0]?o1[1]-o2[1]:o1[0]-o2[0]);

        //初始化入度数组、标记数组、后置城市数组
        int[] Indeg=new int[N];
        boolean[] v=new boolean[N];
        int[][] limit=new int[N][N];

        //给后置城市数组和入度数组赋值
        for(Point p:list){
            limit[p.x-1][p.y-1]=1;
            Indeg[p.y-1]++;
        }

        //如果入度为0，则表示可以访问，加入到队列，并且访问标记置为true
        for(int i=0;i<N;i++){
            if(Indeg[i]==0){
                v[i]=true;
                queue.offer(new int[]{A[i],i});
            }
        }

        //记录最多可去城市数目
        int cnt=0;
        while(!queue.isEmpty()){
            int[] city=queue.poll();
            int cost=city[0];
            int id=city[1];
            //如果剩余花费不够，则直接跳出循环
            if(V<cost) break;
            V-=cost;
            cnt++;
            //如果存在后置城市，将对应后置城市入度减一
            for(int j=0;j<N;j++){
                if(limit[id][j]==1){
                    Indeg[j]--;
                }
            }
            //如果入度为0，并且没有访问过，则加入到队列，并且访问标记置为true
            for(int i=0;i<N;i++){
                if(!v[i]&&Indeg[i]==0){
                    v[i]=true;
                    queue.offer(new int[]{A[i],i});
                }
            }
        }

        return cnt;

    }
}

3.复杂度分析

时间复杂度：当队列里的某个城市被选之后，遍历所有的城市，通过标记数组+入度数组判断哪些城市可以入队，会有很多重复的判断，这个重复判断的操作次数为 $O(n^2)$ 级别，如果没有重复判断，正常入队的城市最多有n个，时间复杂度是 $O(nlog_2n)$ ，所以最终的时间复杂度是 $O(n^2)$ 。
空间复杂度：需要额外大小为 $n^2$ 的limit数组，与方法一相比，多了标记数组的空间开销，空间复杂度是 $O(n^2)$ 。