题意：给出一棵树。。。求距离每个点的最远距离是多少。。。
思路：最远距离什么的。。能想到树的直径。。。但是有什么关系呢？ 我们在求树的直径的时候。。。直径的两个端点是可以知道的。。。如果再从两个端点分别做两次bfs。。。每个点取两个距离的较大值就是答案。。。。？
1A.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
/* *********************************************** Author :111qqz Created Time :2016年07月12日 星期二 13时29分49秒 File Name :code/hdu/2196.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <ctime> #define fst first #define sec second #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; #define pi pair < int ,int > #define MP make_pair using namespace std; const double eps = 1E-8; const int dx4[4]={1,0,0,-1}; const int dy4[4]={0,-1,1,0}; const int inf = 0x3f3f3f3f; const int N=1E4+7; int n,m; vector < pi >edge[N]; int d[N]; int ans[N]; bool vis[N]; int beg,lst; int far; void bfs( int s) { ms(d,0x3f); ms(vis,false); queue<int>q; q.push(s); vis[s] = true; d[s] = 0 ; while (!q.empty()) { int u = q.front(); q.pop(); int siz = edge[u].size(); for ( int i = 0 ; i < siz; i++) { int v = edge[u][i].fst; if (vis[v]) continue; vis[v] = true; d[v] = d[u] + edge[u][i].sec; q.push(v); } } } int main() { #ifndef ONLINE_JUDGE freopen("code/in.txt","r",stdin); #endif while (~scanf("%d",&n)) { ms(ans,0); for ( int i = 1 ; i <= n ; i++) edge[i].clear(); for ( int i = 2 ; i <= n ; i++) { int u,v,w; u = i; scanf("%d %d",&v,&w); edge[v].push_back(make_pair(u,w)); edge[u].push_back(make_pair(v,w)); } bfs(1); int mx = 0; for ( int i = 1 ; i <= n ; i++) { if (d[i] > mx) { mx = d[i]; lst = i ; } } // cout<<"lst:"<<lst<<endl; far = 0 ; bfs(lst); for ( int i = 1 ; i <= n ; i++) { if (d[i]>far) { far = d[i]; beg = i ; } } // cout<<"far:"<<far<<endl; // cout<<"beg:"<<beg<<endl; bfs(beg); for ( int i = 1 ; i <= n ; i++) ans[i] = max(ans[i],d[i]); bfs(lst); for ( int i = 1 ; i <= n ;i++) ans[i] = max(ans[i],d[i]); for ( int i = 1 ; i <= n ; i++) cout<<ans[i]<<endl; } #ifndef ONLINE_JUDGE fclose(stdin); #endif return 0; } |
20161201upd:更新一个dp的做法（虽然用树的直径搞貌似要更好想也更直观，不过为了体会dp的思想嘛。。。）
这道题要求的是从树上一点出发的最长路。考虑有根树，不难想到，从树上一点u出发的最长路必然是下述两种情况之一：（1）第一步向下走，（一直向下，走到某叶子节点）（2）第一步向上走。考虑树形DP：dp[0][u] : 从节点u向下走的最长路径dp[1][u] : 从节点u向下走的次长路径这里，次长路径的含义是：与某条选定的最长路径不重合的路径中最长的路径。dp[2][u] : 从节点u第一步向上走所能获得的最长路径注意：考虑如何转移对于节点u，考虑u的所有子节点v，用dp[0][v]来更新dp[0][u], dp[1][u]。至于dp[2][u], 仍考虑两种情况：（1）第二步向下走, 这样便转移到u的父亲节点f第一步向下走的情况。这时还要考虑用dp[0][f]还是dp[1][f]来更新dp[2][u]:（kk:因为如果第一步向上走，然后又从父亲节点回到当前节点，那么这是无意义，并且等于没有更新向上走的情况，这也是要求次小的原因）如果从f第一步走到u能走出一条从f向下的最长路，就用dp[1][f]来更新dp[2][u]，否则用dp[0][f]。（2）第二步仍向上走，这样便转移到f第一步向上走的情况，即dp[2][f]。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
/* *********************************************** Author :111qqz Created Time :2016年12月01日 星期四 09时03分08秒 File Name :code/hdu/r2196.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <ctime> #define fst first #define sec second #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; #define pi pair < int ,int > #define MP make_pair using namespace std; const double eps = 1E-8; const int dx4[4]={1,0,0,-1}; const int dy4[4]={0,-1,1,0}; const int inf = 0x3f3f3f3f; const int N=1E4+7; int n; vector < pi > edge[N]; int dp[3][N]; //dp[0][i]:从节点i出发第一步向下走能达到的最远距离。 //,dp[1][i]：从节点i出发第一步向下走，能达到的次远距离（要求与最远距离的路径不相交） //dp[2][i]:从节点i出发第一步向上走，能达到的最远距离。 void dfs( int u,int pre) { for ( auto x : edge[u]) { int v = x.fst; int w = x.sec; if (v==pre) continue; dfs(v,u); if (w+dp[0][v]>dp[0][u]) { dp[1][u] = dp[0][u]; dp[0][u] = w + dp[0][v]; }else if (w + dp[0][v]>dp[1][u]) dp[1][u] = w + dp[0][v]; } } void dfs2( int u,int pre) { for ( auto x : edge[u]) { int v = x.fst; int w = x.sec; if (v == pre) continue; if (w + dp[0][v]==dp[0][u]) dp[2][v] = max(dp[2][v],dp[1][u] + w); else dp[2][v] = max(dp[2][v],dp[0][u] + w); dp[2][v] = max(dp[2][v],dp[2][u] + w); dfs2(v,u); //调用成了dfs，调试了半天。。。智力－２ } } int main() { #ifndef ONLINE_JUDGE freopen("code/in.txt","r",stdin); #endif while (~scanf("%d",&n)) { ms(dp,0); for ( int i = 1 ; i<= n ; i++) edge[i].clear(); for ( int i = 2 ;i <= n ; i++) { int u,v,w; u = i ; scanf("%d %d",&v,&w); edge[u].push_back(MP(v,w)); edge[v].push_back(MP(u,w)); } dfs(1,-1); dfs2(1,-1); for ( int i = 1 ; i <= n ; i++) printf("%d\n",max(dp[0][i],dp[2][i])); } #ifndef ONLINE_JUDGE fclose(stdin); #endif return 0; } |
说点什么
您将是第一位评论人！