POJ 3160 缩点+拓扑排序+简单dp

题目链接： http://poj.org/problem?id=3160

题目大意：

　　给定一个有向图，每个点有权值，要求选定一个起点，从该点出发一直走，走出一条路径，该路径上的所有点的权值可取可不取，要求最大的权值和，注意可以重复走点，但是权值只可以加一次。

分析：

　　显然，如果权值<=0，一律赋为0,

　　由输入数据，我们用Tarjan算法缩点得到一个有向无环图，同时注意每个强连通分量（SCC）的权值是该分量所含点的权值和;

　　得到的有向无环图（DAG）可能是一个有多个入度为0的点的图，为了方便dp，进行拓扑排序，然后简单更新即可，具体见代码。

　　（我自己对这类题目的理解就是：进行拓扑排序可以方便dp，不会有后效性）

代码：

poj3160

  1 /*3160    Accepted    1436K    79MS    C++    2940B    2012-06-09 20:36:23*/
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <iostream>
  6 #include <algorithm>
  7 #include <vector>
  8 using namespace std;
  9 
 10 #define mpair make_pair
 11 #define pii pair<int,int>
 12 #define MM(a,b) memset(a,b,sizeof(a));
 13 typedef long long lld;
 14 typedef unsigned long long u64;
 15 template<class T> bool up_max(T& a,const T& b){return b>a? a=b,1 : 0;}
 16 template<class T> bool up_min(T& a,const T& b){return b<a? a=b,1 : 0;}
 17 #define maxn 30020
 18 
 19 int n,m;
 20 int val[maxn];
 21 vector<int>g[maxn], adj[maxn];
 22 
 23 void Read(){
 24     for(int i=0;i<n;++i){
 25         scanf("%d", val+i);
 26         if( val[i]<0 ) val[i]= 0;
 27     }
 28     for(int i=0;i<n;++i) g[i].clear(); /// clear();
 29     for(int i=1;i<=m;++i){
 30         int x,y;
 31         scanf("%d%d", &x, &y);
 32         g[x].push_back(y);
 33     }
 34 }
 35 
 36 int c[maxn];
 37 int Bcnt, Index, Top;
 38 int low[maxn], dfn[maxn], stack[maxn], belong[maxn];
 39 bool vis[maxn];
 40 void Init_tarjan(){
 41     Bcnt= Index= Top= 0;
 42     for(int i=0;i<n;++i) low[i]= dfn[i]= vis[i]= 0;
 43 }
 44 void Tarjan(int u){
 45     stack[++Top]= u;
 46     vis[u]= 1;
 47     low[u]= dfn[u]= ++Index;
 48     for(int i=0;i<g[u].size();++i){
 49         int v= g[u][i];
 50         if( !dfn[v] ){
 51             Tarjan(v);
 52             up_min( low[u], low[v] );
 53         }
 54         else if( vis[v] )
 55             up_min( low[u], dfn[v] );
 56     }
 57     if( low[u]==dfn[u] ){
 58         c[ ++Bcnt ] = 0;
 59         int v;
 60         do{
 61             v= stack[Top--];
 62             vis[v]= 0;
 63             belong[v]= Bcnt;
 64             c[Bcnt]+= val[v];
 65         }while(u!=v);
 66     }
 67 }
 68 
 69 int in[maxn];
 70 void dfs(int u){
 71     vis[u]= 1;
 72     for(int i=0;i<g[u].size();++i){
 73         int v= g[u][i];
 74         if( belong[u]!=belong[v] ){
 75             adj[ belong[u] ].push_back( belong[v] );
 76             in[ belong[v] ]++;
 77         }
 78         if( !vis[v] ) dfs(v);
 79     }
 80 }
 81 
 82 int *que;
 83 int dp[maxn];
 84 int Topsort(){
 85     int head=0, tail= 0;
 86     fill( dp, dp+1+Bcnt, 0 );
 87     for(int i=1;i<=Bcnt;++i) if( in[i]==0 ) { que[tail++]= i; dp[i]= c[i];}
 88     while( head<tail ){
 89         int u= que[head++];
 90         for(int i=0;i<adj[u].size();++i){
 91             int v= adj[u][i];
 92             if( --in[v] == 0 )
 93                 que[tail++]= v;
 94         }
 95     }
 96 
 97     for(int i=0;i<tail;++i){
 98         int u= que[i];
 99         for(int j=0;j<adj[u].size();++j){
100             int v= adj[u][j];
101             up_max( dp[v], dp[u]+c[v] );
102         }
103     }
104     return *max_element( dp+1, dp+1+Bcnt );
105 }
106 
107 int solve(){
108     Init_tarjan();
109     for(int i=0;i<n;++i){
110         if( !dfn[i] )
111             Tarjan(i);
112     }
113 
114     MM( vis, 0 );
115     for(int i=1;i<=Bcnt;++i) adj[i].clear(), in[i]= 0;
116     for(int i=0;i<n;++i){
117         if( !vis[i] )
118             dfs(i);
119     }
120     que= stack; ///
121     return Topsort();
122 }
123 
124 int main()
125 {
126     // freopen("poj3160.in","r",stdin);
127     while( cin>>n>>m ){
128         Read();
129         cout<< solve() << endl;
130     }
131 }