2020/04/15华为机试题目三

测试用例
第一行 函数个数 每个函数调用的函数个数
接下来每一行 函数栈容量 调用的函数编号
求有向图最大点权路径和 如果有环返回R
5 2 3 1 0 0
1 20 2 3
2 30 3 4 5
3 50 4
4 60
5 80

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
struct Node{
    //栈容量
    int v;
    //有向图 目的点
    vector <int> number;
    //有几个目的点
    int k;
    //以此结点为起点 的路径 是否有环
    bool flag = false;
}Node[10010];
int N;
vector<int> ans;
void dfs(int i,int temp,int &sum){

   //回溯将全部路径点权和放进ans  ans保存的是全部的路径点权和
    if(Node[i].number.size()==0){
        ans.push_back(sum);
        return ;
    }
    for(int j = 0;j<Node[i].number.size();j++){
    if(Node[i].number[j]==temp){
            Node[i].flag = true;
            return;
        }
         sum = sum+ Node[Node[i].number[j]].v;
         dfs(Node[i].number[j],temp,sum);
         sum = sum -  Node[Node[i].number[j]].v;
    }
}

int main() {
    cin>>N;
    for(int i =1;i<=N;i++){
        int value;
        cin>>value;
        Node[i].k = value;
    }
    for(int  i = 1;i<=N;i++){
        int M;
        cin>>M;
        int va;
        cin>>va;
        Node[M].v = va;
        for(int j = 0;j<Node[M].k;j++){
            int number;
            cin>>number;
            Node[M].number.push_back(number);
        }
    }
    for(int i = 1;i<=N;i++){
        int s=Node[i].v;
        dfs(i,i,s);
        //判断是否有环
        if(Node[i].flag){
            cout<<"R"<<endl;
            return 0;
        }
    }
    sort(ans.begin(),ans.end());
    cout<<ans[ans.size()-1]<<endl;
    return 0;
}