http://acm.timus.ru/problem.aspx?space=1&num=1463

樹形DP??

此題有個陷阱?? 就是圖的本身是一個森林 不是樹

由于所有 happiness 的值都為非負 所有最優路徑一定是從一個葉子節點到另一個葉子節點（當然 兩個節點可能一樣）

思路：

包含一個節點 和 兩個節點的 樹特殊處理

對應3個節點以及3個節點以上的樹 一定能找到一個初度 大于等于2 的點 以此點為根節點更新

對于這個樹? dfs? 記錄每個點向下的第一最優路徑選擇 和第二最優路徑選擇

然后不斷向上更新

最后 把所有向下路徑至少兩條的節點 將此類節點的兩個最優路徑 連起來的路徑進行和最終答案比較 擇優而選

剛開始用 vector 建圖 結果超內存了 看來 vector 的時間和空間占用都比較大

代碼及其注釋：

#include<iostream> #include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #include<vector> #include<set> #include<map> #include<string> #include <iomanip> using namespace std; const int N=50005; int head[N],I; struct node {int j,h,next; }side[N*2];//雙向邊 int out[N],sub[N],next1[N],next2[N];//初度 ，子樹最優長度 ，第一選擇路徑，第二選擇路徑 vector<int>ans; int a[N]; void Add(int i,int j,int h) {side[I].j=j;side[I].h=h;side[I].next=head[i];head[i]=I++; } int Optimal(int i)//以此點為根節點的樹中 最優路徑長度 {if(out[i]==0)return a[i];if(out[i]==1)return a[i]+a[side[head[i]].j]+side[head[i]].h;return a[i]+side[next1[i]].h+sub[side[next1[i]].j]+side[next2[i]].h+sub[side[next2[i]].j]; } int Fhappy(int x,int i)//從x節點選擇i路徑向下的路徑長度 {return (side[i].h+sub[side[i].j]); } int dfs(int x,int pre) {for(int t=head[x];t!=-1;t=side[t].next){int l=side[t].j;if(l==pre)continue;dfs(l,x);if(next2[x]==-1||Fhappy(x,t)>Fhappy(x,next2[x]))//更新最優選擇路徑next2[x]=t;elsecontinue;if(next1[x]==-1||Fhappy(x,next2[x])>Fhappy(x,next1[x]))//更新最優選擇路徑swap(next2[x],next1[x]);}sub[x]=a[x];if(next1[x]!=-1)sub[x]+=Fhappy(x,next1[x]);return sub[x]; } int main() {//freopen("data.txt","r",stdin);int n,m;while(scanf("%d %d",&n,&m)!=EOF){memset(head,-1,sizeof(head));I=0;memset(next1,-1,sizeof(next1));memset(next2,-1,sizeof(next2));memset(out,0,sizeof(out));for(int i=1;i<=n;++i)scanf("%d",&a[i]);int l,r,h;while(m--){scanf("%d %d %d",&l,&r,&h);Add(l,r,h);Add(r,l,h);++out[l];++out[r];}int k=-1;for(int i=1;i<=n;++i){if(out[i]>=2&&next1[i]==-1){dfs(i,-1);if(k==-1||Optimal(i)>Optimal(k))k=i;}}for(int i=1;i<=n;++i){if(out[i]>=3){if(k==-1||Optimal(i)>Optimal(k))k=i;}else if(out[i]==0)//只有一個點才情況{if(k==-1||Optimal(i)>Optimal(k))k=i;}else if(out[i]==1&&out[side[head[i]].j]==1)//只有兩個點的情況{if(k==-1||Optimal(i)>Optimal(k))k=i;}}if(out[k]<=1){printf("%d\n",Optimal(k));if(out[k]==0){printf("1\n");printf("%d\n",k);}else{printf("2\n");printf("%d %d\n",k,side[head[k]].j);}continue;}ans.clear();ans.push_back(k);//將最優路徑存到 ans 里面int tmp=side[next1[k]].j;do{ans.push_back(tmp);if(next1[tmp]==-1)break;tmp=side[next1[tmp]].j;}while(true);tmp=side[next2[k]].j;do{ans.insert(ans.begin(),tmp);if(next1[tmp]==-1)break;tmp=side[next1[tmp]].j;}while(true);printf("%d\n",Optimal(k));printf("%d\n",ans.size());for(unsigned int i=0;i<ans.size();++i)printf("%d ",ans[i]);printf("\n");}return 0; }

?

轉載于:https://www.cnblogs.com/liulangye/archive/2012/10/29/2744299.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的1463. Happiness to People!的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。