题解 | #旅行Ⅰ#

NC522 旅行Ⅰ
题解一：优先队列，拓扑排序
题解思路：
 首先，如果将list中限制条件构建成一个图。如图：

 在去2号城市之前必须先去1号城市， 转换成有向图1--->2; 我们使用 vector<vector<int> > in(N+1,vector<int>(N+1,0)); 表示有向图的邻接矩阵，第一行用来代表每个结点的入度数。
 其次， 将所有入度为0的结点加入到优先队列，并且按照花费从小到大排序。
 最后，利用拓扑排序的思想，每次从优先队列中取出一个元素，如果当前V-当前城市花费>=0,那么就将可到达城市数+1，否则就返回答案。

过程： 将1，3入队；接着将1出队，将到1城市的花费cost与 V比较，如果可到达，那么就将V-cost,并将以1为前置的城市的入度数减1；最后，再次找入度为0的结点，加入到优先队列中。
复杂度分析：
 时间复杂度： : 每个城市都需要遍历一次，优先队列出队和入队需要logN,每次之后都与要遍历去改变结点的入度 所以总时间复杂度：O(N^2logN)
 空间复杂度： : 保存有向图的邻接矩阵</int></int>

**实现如下：**

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param N int整型 N
     * @param V int整型 V
     * @param A int整型vector A
     * @param list Point类vector List
     * @return int整型
     */
    // 首先，建图，先找到入度为0的结点 开始拓扑排序
    // 不过，如果有多个入度为0的结点，那么就优先找花费小的结点
    struct cmp1{
        bool operator() (const pair<int, int> a,const pair<int,int> b){
            return a.second > b.second;  //按花费从小到达排序
        }
    };
    // pair<int,int>  表示 城市i 到达i所需要的费用
    priority_queue<pair<int,int>,vector<pair<int,int>>,cmp1> st; //用来保存入度为0的结点

    int Travel(int N, int V, vector<int>& A, vector<Point>& list) {
        // write code here
        vector<vector<int> > in(N+1,vector<int>(N+1,0));  //用来保存邻接矩阵和每个结点的入度数
        //邻接矩阵和入度数 
        for(auto it : list){
            in[it.x][it.y] = 1;
            in[0][it.y]+=1;
        }
        int ans = 0;  //最终可达到城市的数目
        for(int i = 1;i<=N;++i){
            if(in[0][i]==0) st.push(make_pair(i, A[i-1]));  //将入度为0的加入到优先队列
        }
        while(!st.empty()){
            pair<int, int> p  = st.top();  //弹出一个元素
            st.pop();
            if(V<p.second)break;  // 如果不足以到达
            V-=p.second;  //将V减去花费
            ans++; //数目加1
            int i = p.first;  
            for(int j = 1;j<=N;j++){
                if(in[i][j]==1){
                    in[0][j]--;  //将以i为前置城市的结点入度减1
                    if(in[0][j]==0) st.push(make_pair(j, A[j-1])); //最后再将入度为0的城市加入优先队列
                }
            }
        }
        return ans;
    }
};

题解二：模拟+标记数组
题解思路： 直接模拟路线过程。同样需要使用一个二维数据记录城市的次序，并且需要用一个标记数组表明城市有无访问过。接着模拟访问，首先依旧是将入度为0的城市入队，
每次还是花费最小的城市出队，然后它的后置城市入度减一。

复杂度分析：
时间复杂度：
空间复杂度：
实现如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param N int整型 N
     * @param V int整型 V
     * @param A int整型vector A
     * @param list Point类vector List
     * @return int整型
     */
    struct cmp1{
        bool operator() (const pair<int, int> a,const pair<int,int> b){
            return a.second > b.second;  
        }
    };
    priority_queue<pair<int,int>,vector<pair<int,int>>,cmp1> st; //用来保存入度为0的结点
    int Travel(int N, int V, vector<int>& A, vector<Point>& list) {
        // write code here
        vector<vector<int> > in(N+1,vector<int>(N+1,0));//用来保存邻接矩阵和每个结点的入度数
        //后置城市数组和入度数组
        for(auto it : list){
            in[it.x][it.y] = 1;
            in[0][it.y]+=1;
        }
        int ans = 0;
        vector<int> vis(N+1,0);
        for(int i = 1;i<=N;++i){
            if(in[0][i]==0) {
                st.push(make_pair(i, A[i-1]));
                vis[i] = 1;  //将其设为访问
            }
        }
        while(!st.empty()){
            pair<int,int> p = st.top();
            st.pop();
            if(V<p.second)break;
            V-=p.second;
            ans++;
            int i = p.first;
            for(int j = 1;j<=N;j++){
                if(in[i][j]==1){
                    in[0][j]--;
                if(in[0][j]==0&&!vis[j]){  //最后再将入度为0的城市加入优先队列并且没有访问过
                    vis[j] = 1;
                    st.push(make_pair(j, A[j-1]));
                }
            }
         }
       }
        return ans;
    }
};