兩次搜索的方法
?
#include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; int N,V[10100]; vector<int>son[10100]; //圖 int MAX[10100],MAXN[10100]; //最大值及其標號 int SMAX[10100],SMAXN[10100]; //次大值及其標號 bool vis[10100]; //標記訪問狀態 void dfs1(int n) //在以n為根節點的子樹上求出節點n到葉子節點距離的最大值 { MAX[n]=SMAX[n]=0; int len=son[n].size(); for(int i=0;i<len;i++) { int k=son[n][i]; //兒子標號 - - dfs1(k); if(SMAX[n]<MAX[k]+V[k]) { SMAX[n]=MAX[k]+V[k]; SMAXN[n]=k; if(SMAX[n]>MAX[n]){ swap(SMAX[n],MAX[n]); swap(SMAXN[n],MAXN[n]); } } } } void dfs2(int n) //求出n的兒子們在樹中能延伸的最大距離(n的最大距離及次大距離已得到) { int len=son[n].size(); vis[n]=1; for(int i=0;i<len;i++) { int k=son[n][i]; if(vis[k]) continue; if(k==MAXN[n]){ if(SMAX[k]<SMAX[n]+V[k]){ SMAX[k]=SMAX[n]+V[k]; SMAXN[k]=n; if(SMAX[k]>MAX[k]){ swap(SMAX[k],MAX[k]); swap(SMAXN[k],MAXN[k]); } } } else{ if(SMAX[k]<MAX[n]+V[k]){ SMAX[k]=MAX[n]+V[k]; SMAXN[k]=n; if(SMAX[k]>MAX[k]){ swap(SMAX[k],MAX[k]); swap(SMAXN[k],MAXN[k]); } } } dfs2(k); } } int main() { int i,j,k,u,v; while(scanf("%d",&N)!=EOF) { for(i=1;i<=N;i++) son[i].clear(); for(i=2;i<=N;i++){ scanf("%d%d",&u,&V[i]); son[u].push_back(i); //i的父親是u } memset(vis,0,sizeof(vis)); dfs1(1); // 測試 // for(i=1;i<=N;i++) printf("~%d ",MAX[i]);printf("\n"); // for(i=1;i<=N;i++) printf("~%d ",SMAX[i]);printf("\n"); memset(vis,0,sizeof(vis)); dfs2(1); for(i=1;i<=N;i++) printf("%d\n",MAX[i]); } return 0; } /* 5 1 1 2 1 3 1 1 1 */
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
