POJ 3592 缩点+拓扑排序+最长路

题目大意：

　　给定一个n*m的地图，有0-9表示某个格子上的value，‘*’表示该格子上有个时空门，可直接到指定的某个格子（可以自行选择是否使用时空门），‘#’表示该格子无法使用，某个格子的value只能被计算一次，问从起点（规定为左上角，我一直把northwest看成了右上角，伤不起）出发，每次只能往下走一格或往右走一格，最多能得到多大的value。

分析：

　　首先根据给定的关系建图，又因为有时空门的存在，所以必须缩点，

　　对缩点后的图进行拓扑排序之后再dp，即可求得最长路。

（PS：这题我看了discuss，发现思路什么的对了，就是一点，起点我自己看成了右上角，伤不起啊~！~）

代码（好像我的比较冗长的）：

poj3592

  1 /*3592    Accepted    428K    0MS    C++    4222B    2012-06-09 16:18:12*/
  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 1640
 18 #define maxm 50
 19 
 20 int n,m,k, nv;
 21 int f[maxm][maxm];
 22 char ch[maxm][maxm];
 23 
 24 vector<int>g[maxn], adj[maxn];
 25 int mark[maxm][maxm];
 26 pii a[maxn], fp[maxn];
 27 
 28 void Read(){
 29     int i,j,x,y;
 30     scanf("%d %d\n", &n, &m);
 31     for(i=0;i<n;++i)
 32         for(j=0;j<m;++j){
 33             f[i][j]= i*m + j + 1;
 34             fp[i*m+j+1]= pii( i, j );
 35         }
 36     nv= n*m;
 37 
 38     k= 0;
 39     for(i=0;i<n;++i){
 40         for(j=0;j<m;++j){
 41             scanf("%c", &ch[i][j]);
 42             if( '*' == ch[i][j] )
 43                 mark[i][j]= ++k;
 44         }
 45         getchar();
 46     }
 47 
 48     for(i=1;i<=k;++i){
 49         scanf("%d%d", &x, &y);
 50         a[i]= pii( x, y );
 51     }
 52 }
 53 
 54 void build_graph(){
 55     int i,j;
 56     for(i=1;i<=nv;++i) g[i].clear();
 57     for(i=0;i<n;++i){
 58         for(j=0;j<m;++j){
 59             if( '#' == ch[i][j] ) continue;
 60 
 61             if( i+1<n && '#'!=ch[i+1][j] ){ /// go down;
 62                 g[ f[i][j] ].push_back( f[i+1][j] );
 63             }
 64             if( j+1<m && '#'!=ch[i][j+1] ){ /// go left;
 65                 g[ f[i][j] ].push_back( f[i][j+1] );
 66             }
 67             if( '*' == ch[i][j] ){ /// can use magic power;
 68                 int t= mark[i][j];
 69                 int x= a[t].first, y= a[t].second;
 70                 if( '#' != ch[x][y] ) ///
 71                     g[ f[i][j] ].push_back( f[x][y] );
 72             }
 73         }
 74     }
 75 }
 76 
 77 int c[maxn]; /// each block's sum-value;
 78 
 79 int Bcnt, Index, Top;
 80 int low[maxn], dfn[maxn], stack[maxn], belong[maxn];
 81 bool inq[maxn];
 82 void Init_tarjan(){
 83     Bcnt= Index= Top= 0;
 84     for(int i=1;i<=nv;++i) low[i]= dfn[i]= inq[i]= 0;
 85 }
 86 void Tarjan(int u){
 87     stack[++Top]= u;
 88     inq[u]= 1;
 89     low[u]= dfn[u]= ++Index;
 90     for(int i=0;i<g[u].size();++i){
 91         int v= g[u][i];
 92         if( !dfn[v] ){
 93             Tarjan( v );
 94             up_min( low[u], low[v] );
 95         }
 96         else if( inq[v] )
 97             up_min( low[u], dfn[v] );
 98     }
 99     if( low[u]==dfn[u] ){
100         ++Bcnt;
101         int v;
102         do{
103             v= stack[Top--];
104             inq[v]= 0;
105             belong[v]= Bcnt;
106             int x= fp[v].first, y= fp[v].second;
107             if( '1'<=ch[x][y] && ch[x][y]<='9' )
108                 c[Bcnt]+= ch[x][y]-'0';
109         }while(u!=v);
110     }
111 }
112 
113 int in[maxn];
114 void build2(int u){
115     inq[u]= 1;
116     for(int i=0;i<g[u].size();++i){
117         int v= g[u][i];
118         if( belong[v] != belong[u] ){
119             adj[ belong[u] ].push_back( belong[v] );
120             ++in[ belong[v] ];
121         }
122         if( !inq[v] ) build2(v); /// here!!!!!!!!!!!!!!!!!!!;
123     }
124 }
125 
126 int *que; ///
127 int dp[maxn];
128 int Topsort(){
129     int i,head=0,tail=0;
130     fill( dp, dp+1+Bcnt, 0 );
131     /// for(i=1;i<=Bcnt;++i) if( in[i]==0 ) { que[tail++]= i; dp[i]= c[i]; }
132     que[tail++]= belong[1]; ///!!!!!!!!!!!!!
133     dp[belong[1]]= c[belong[1]];
134 
135     while( head<tail ){
136         int u= que[head++];
137         for(int i=0;i<adj[u].size();++i){
138             int v= adj[u][i];
139             if( --in[v] == 0 )
140                 que[tail++]= v;
141         }
142     }
143 
144     for(i=0;i<tail;++i){
145         int u= que[i];
146         for(int j=0;j<adj[u].size();++j){
147             int v= adj[u][j];
148             up_max( dp[v], dp[u]+c[v] );
149         }
150     }
151 
152     int ans= 0;
153     for(i=0;i<tail;++i) up_max( ans, dp[ que[i] ] ); /// que[i];
154     return ans;
155 }
156 
157 int solve(){
158     build_graph();
159     Init_tarjan();
160     fill( c, c+nv+1, 0 );
161     Tarjan(1); ///
162 
163     for(int i=1;i<=Bcnt;++i) adj[i].clear(), inq[i]= 0, in[i]= 0;
164     build2(1);
165 
166     que= stack;
167     return Topsort();
168 }
169 
170 int main()
171 {
172     //freopen("poj3592.in","r",stdin);
173     int T;
174     cin>>T;
175     while(T--){
176         Read();
177         cout<< solve() <<endl;
178     }
179 }