蓝桥杯2013年第四届真题-大臣的旅费 （C++代码） 动态规划AC思路及代码

解题思路:

        这道题难点就是不知道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时间不准;

注意事项:

        1.建树过程由于题中没说节点输入的顺序，所以保险起见，就当输入是乱序，然后根据根节点1开始建树

        2.动态规划的顺序应该是从节点的高度大的到小的，所以需要保存节点高度用数组p_h实现,而对应的高度的所有节点用vector h_p实现。

        3.w[i][j]用数组无法实现，开不下这么大的空间，所以用map<pair,int>去实现查找，c99的map查找复杂度是nlogn，小于算法时间复杂度所以可以不担心，实在强迫想快点可以看我在本题实现的hashmap，代替自带的map。

参考代码:

#include <vector>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <queue>
#define _for(i,a,b) for(int i=a;i<b;i++)
#define _unfor(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],maxh=0,p_h[111111],ans=0;
vector<int> son[111111],G[111111],h_p[111111];
map<pair<int,int>,int> W;

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;
    }
    //建树
    queue<int> q;
    q.push(1);h_p[0].push_back(1);
    while(!q.empty()){
        int v=q.front(),len=G[v].size();q.pop();
        vis[v]=1;
        _for(k,0,len){
            int e=G[v][k];
            if(!vis[e]){
                vis[e]=1;
                son[v].push_back(e);
                q.push(e);
                maxh=max(maxh,p_h[e]=p_h[v]+1);
                h_p[p_h[e]].push_back(e);
            }
        }
    }
    //动态规划
    _unfor(h,maxh,0){
        int len=h_p[h].size();
        _for(k,0,len){
            int i=h_p[h][k],_max=0,_cmax=0;
            int len2=son[i].size();
            _for(k2,0,len2){
                int j=son[i][k2],t;
                pair<int,int> pr(i>j?i:j,i>j?j:i);
                t=W[pr]+d[j];
                if(t>_cmax)if((_cmax=t)>_max)swap(_max,_cmax);
                ans=max(ans,_max+_cmax);
            }
            d[i]=_max;
        }
    }
    cout<<(LL)(ans+1)*ans/2+ans*10<<endl;
}

Hash_Map实现代码：

struct hmap{
    static const int hashsize=30007;
    map<pair<int,int>,int> mmp[hashsize];
    int add(int a,int b,int c){
        int key=(a^b+b)%hashsize;
        pair<int,int> pr(a,b);
        mmp[key][pr]=c;
    }
    int get(int a,int b){
        int key=(a^b+b)%hashsize;
        pair<int,int> pr(a,b);
        return mmp[key][pr];
    }
};