CSU暑期集訓day05_DFS_單源最大權路徑

NO IMAGE

題目:

有一棵由N個結點構成的樹,每一條邊上都有其對應的權值。現在給定起點,求從該點出發的一條路徑(至少有一條邊)使得這條路徑上的權值之和最大,並輸出這個最大值。

Input

第一行一個正整數T,代表資料組數。每組資料第一行兩個正整數n(2<=n<=10^5),s(1<=s<=n),分別表示樹結點數目以及給定的起點,點的編號從1至N。接下來M行,每行三個整數x,y,z,(1<=x,y<=n,|z|<=1000),代表編號為x和y的點之間有一條權值為z的雙向邊。

Output

每組資料輸出一行,即所找到路徑的最大權值(格式參見樣例)。

Sample Input

2
3 1
1 2 10
1 3 5
5 5
1 5 70
4 3 100
5 3 -10
2 5 60

Sample Output

Case #1: 10
Case #2: 90

解題思路:

    這題思路比較明確,由指定點出發深度優先遍歷,無路可走的時候就可以結束,將當前路徑權值參與比較選出最大的。我做這道題的時候卻一波三折,主要是在糾結結點的儲存問題,因為題目要求點的數目較多,直接設定二維陣列儲存會報錯,然後我改用vector弄個二維陣列,卻還是報錯,又改用結構體,結構體元素中有個鄰居陣列,點的數目有100000,也只好給鄰居陣列也設定大小100000,然後再用vector,還是報錯,,,,所幸最後終於弄對了,出現這種情況的根本原因還是自己太菜了,對stl使用不熟練,不靈活。

程式碼:

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

struct edge{
    int num;
    int weight;
};
vector<edge> ve[100002];

int n,s;
bool visi[100002];
long long int maxa=0;

void dfs(int s,int ans){
    visi[s]=true;
    for(int i=0;i<ve[s].size();i ){
        if(!visi[ve[s][i].num]){
            dfs(ve[s][i].num,ans ve[s][i].weight);
        }
    }  
    if(ans>maxa)maxa=ans;   
    visi[s]=false;
}

int main(){
    int t;
    cin>>t;
    for(int c=1;c<=t;c ){    
        maxa=0;
        memset(visi,false,sizeof(visi));    
        cin>>n>>s;
        for(int i=0;i<=n;i )ve[i].clear();        
        int x,y,z;
        int e=n-1;
        while(cin>>x>>y>>z){          
            edge a;
            a.num=y;
            a.weight=z;
            ve[x].push_back(a);
            a.num=x;
            ve[y].push_back(a);
            e–;
            if(e==0)break;
        }     
        dfs(s,0);      
        cout<<“Case #”<<c<<“: “<<maxa<<endl;        
    } 
    system(“pause”);
    return 0;
}