蓝桥杯2013年第四届真题-大臣的旅费 （C++代码）动态规划记忆化搜索

解题思路:
        

        这道题难点就是不知道n的最大值。
        由题可知，有n-1条边n个结点且连通，那么显然这个图是一棵树。

        定义d[i]=从节点i出发往下走的最长路径，则状态转移方程：

                   d[i]=max{ d[i], w[i][j]+d[j] }, j属于{i的儿子}

        在求解d[i]的过程中，我们可以顺便保存一下 w[i][j]+d[j] 的第二大值cmax。

        那么答案就是 {d[i]+cmax},i属于{所有结点}。

        时间复杂度O(T)=O(nlogn), 本题AC耗时:30ms(使用自己写的hashmap就是20ms)当然这个OJ时间不准;

注意事项:

        

参考代码:

#include <vector>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#define _for(i,a,b) for(int i=a;i<b;i++)
#define RI(a) scanf("%d",&a)
using namespace std;
typedef long long LL;
int d[111111],n,vis[111111],ans=0;
vector<int> G[111111];
map<pair<int,int>,int> W;

int dfs(int i){
    if(d[i])return d[i];
    vis[i]=1;
    int m1=0,m2=0,len=G[i].size();
    _for(k,0,len)if(!vis[G[i][k]]){
        vis[G[i][k]]=1;
        pair<int,int> pr(i>G[i][k]?i:G[i][k],i>G[i][k]?G[i][k]:i);
        int t=W[pr]+dfs(G[i][k]);
        if(t>m2)if((m2=t)>m1)swap(m1,m2);
        ans=max(ans,m1+m2);
    }
    return d[i]=m1;
}

int main(){
    RI(n);
    _for(i,1,n){
        int a,b,c;
        RI(a);RI(b);RI(c);
        G[a].push_back(b);
        G[b].push_back(a);
        pair<int,int> pr(a>b?a:b,a>b?b:a);
        W[pr]=c;
    }
    dfs(1);
    cout<<(LL)(ans+1)*ans/2+ans*10<<endl;
}