1463. Happiness to People!

Time limit: 1.0 second Memory limit: 64 MB

Every Santa Claus wants to surprise children with his presents. This year Santa Claus Petrovich wants to surprise children of remote Cuckooland. He is sure that in order to make a real impression he should choose a route without repeating towns. In order to bring as much happiness as possible, he plans to visit the most populated places. Petrovich took a map of Cuckooland and connected with lines some pairs of towns where, he's sure, people will wait for him. He decided not to fly between towns that are not connected. It turned out that if Petrovich can fly (using one or several flights) from town i to town j, then there is exactly one way to do this. Petrovich can start his trip in any of the towns.

Petrovich knows that when he arrives in town i, the population feels happiness A_i. And when Petrovich flies from town i to town j, he bestows happiness C_ij. The same amount of happiness is bestowed if he flies from j to i. Help Santa Claus Petrovich to maximize the amount of happiness that he can bring to people.

Input

The first line contains the number N (1 ≤ N ≤ 50000) of towns in Cuckooland and the number K of pairs of towns that are connected. The second line contains numbersA_i (i = 1..N); A_i ≤ 10000. Each of the following K lines contains three numbers a, b, c, which mean that when Petrovich flies from town a to town b he brings happiness c (a ≠ b; c ≤ 10000). All numbers in the input are whole and nonnegative.

Output

The first line of the output must contain the maximal amount of happiness felt by the people of Cuckooland. The second line must contain the length L of the optimal route of Santa Claus Petrovich. The third line must contain the optimal route (L numbers separated with a space). If there are several answers, you may output any of them.

Samples

input	output
2 1 1 1 1 2 1	3 2 1 2
8 7 1 5 4 6 10 1 2 2 1 2 1 2 3 10 2 4 1 4 5 1 4 6 2 6 7 2 6 8 3	37 4 5 4 2 3

Problem Author: Alexander Toropov, special thanks to Alexander Ipatov Problem Source: Ural SU Contest. Petrozavodsk Winter Session, January 2006

***************************************************************************************

树状dp和图论思想有许多相似之处，都要深搜找路径经典不过这个树状dp有许多中间需要处理的地方和以前看的树状dp感觉要难，还是自己学艺不精，参考了讲解和代码；

***************************************************************************************

  1 #include<iostream>
  2 #include<cstring>
  3 #include<string>
  4 #include<cstdio>
  5 #include<cmath>
  6 #include<vector>
  7 #include<queue>
  8 #include<stack>
  9 using namespace std;
 10 typedef long long LL;
 11 typedef pair<LL,LL> pLL;
 12 bool vis[50011];
 13 vector<pLL>a[50011];
 14 queue<int>q;
 15 stack<int>stk;
 16 int dp[50011][2],p[50011][2];
 17 int n,m,i,j,k;
 18 int val[50011];
 19 int suma,ans;
 20 int root;
 21 void input()
 22 {
 23     cin>>n>>m;
 24     suma=1;
 25     for(i=1;i<=n;i++)
 26       cin>>val[i];
 27     for(i=0;i<m;i++)//存邻点
 28      {
 29          pLL  temp;
 30          int st,en,w;
 31          cin>>st>>en>>w;
 32          temp.first=st,temp.second=w,a[en].push_back(temp);
 33          temp.first=en,temp.second=w,a[st].push_back(temp);
 34      }
 35 
 36 }
 37 void  dfs(int x)//深搜求最大值
 38  {
 39      dp[x][0]=dp[x][1]=0;//0和1分别代表以x为根的左右
 40      p[x][0]=p[x][1]=-1;
 41      int size=a[x].size();
 42      vis[x]=true;
 43      for(int i=0;i<size;i++)
 44       {
 45        int ds=a[x][i].first;
 46        int w=a[x][i].second;
 47         if(!vis[ds])
 48          {
 49              dfs(ds);
 50              if(dp[ds][1]+w>=dp[x][1])
 51               {
 52                   dp[x][0]=dp[x][1];
 53                   p[x][0]=p[x][1];
 54                   dp[x][1]=dp[ds][1]+w;
 55                   p[x][1]=ds;
 56               }
 57               else if(dp[ds][1]+w>dp[x][0])
 58                   {
 59                       dp[x][0]=dp[ds][1]+w;
 60                       p[x][0]=ds;
 61                   }
 62 
 63 
 64 
 65          }
 66       }
 67       dp[x][1]+=val[x];
 68       dp[x][0]+=val[x];
 69       if(dp[x][1]+dp[x][0]-val[x]>ans)//多加了个根
 70         {
 71             ans=dp[x][1]+dp[x][0]-val[x];
 72             root=x;
 73         }
 74  }
 75  int findpath1(int rt)//找路径
 76    {
 77        int lv;
 78        int suma=1;
 79        while(!stk.empty())stk.pop();
 80        stk.push(rt);
 81        for(lv=p[rt][1];lv!=-1;lv=p[lv][1])
 82         {
 83             stk.push(lv);
 84             suma++;
 85         }
 86        return suma;
 87    }
 88  int findpath2(int rt)
 89    {
 90        int lv;
 91        int suma=0;
 92        while(!q.empty())q.pop();
 93        for(lv=p[rt][0];lv!=-1;lv=p[lv][1])
 94        {
 95            q.push(lv);
 96            suma++;
 97        }
 98        return suma;
 99    }
100    void  solve()
101    {
102        memset(vis,false,sizeof(vis));
103        memset(p,-1,sizeof(p));
104        memset(dp,0,sizeof(dp));
105        ans=-1;
106        for(int is=1;is<=n;is++)
107         if(!vis[is])
108          dfs(is);
109        cout<<ans<<endl;
110        int a0=findpath1(root);
111        int b0=findpath2(root);
112        cout<<a0+b0<<endl;

113        while(!stk.empty())//根据栈和队列的特性
114         {
115             cout<<stk.top()<<' ';
116             stk.pop();
117         }
118         while(!q.empty())
119          {
120              cout<<q.front()<<' ';
121              q.pop();
122          }
123          cout<<endl;
124 
125    }
126    int main()
127    {
128        input();
129        solve();
130        return 0;
131    }

View Code

1463. Happiness to People!