HDU 1224 无环有向最长路

用bellman_ford的方法，将中间不断取较小值，修改为取较大值就可以了

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 using namespace std;

 const int N = ;

 int dp[N] , k , first[N] , val[N] , x , y , fa[N] , rec[N];

 struct Edge{

     int x , y , next , d;

 }e[N*N];

 void add_edge(int x , int y , int d)

 {

     e[k].x = x , e[k].y = y , e[k].next = first[x] , e[k].d = d;

     first[x] = k++;

 }

 int main()

 {

     int T , n , cas = ;

     scanf("%d" , &T);

     while(T--){

         scanf("%d" , &n);

         for(int i =  ; i<=n ; i++)

             scanf("%d" , val+i);

         val[n+] = ;

         int m;

         scanf("%d" , &m);

         k=;

         for(int i =  ; i<m ; i++){

             scanf("%d%d" , &x , &y);

             add_edge(x , y , val[y]);

         }

         memset(dp ,  , sizeof(dp));

         memset(fa ,  , sizeof(fa));

         for(int i =  ; i<=n ; i++){

             for(int j =  ; j<k ; j++){

                 int u = e[j].x , v = e[j].y;

                 if(dp[v] < dp[u] + e[j].d){

                     dp[v] = dp[u] + e[j].d;

                     fa[v] = u;

                    // cout<<"here: "<<u<<" "<<v<<" "<<fa[v]<<" "<<dp[v]<<endl;

                 }

             }

         }

         printf("CASE %d#\npoints : %d\ncircuit : " , ++cas , dp[n+]);

         int cnt =  , la = n+;

         rec[cnt++] = ;

         while(fa[la]){

             rec[cnt++] = fa[la];

             la = fa[la];

         }

         for(int i = cnt- ; i>= ; i--)

             printf("%d->" , rec[i]);

         printf("%d\n" , rec[]);

         if(T>) puts("");

     }

     return ;

 }