链接：http://poj.org/problem?id=3592
题意：题目大意：给定一个矩阵，西南角为出发点，每个单位都有一订价值的金矿（＃默示岩石，不成达，*默示时佛门，可以达到指定单位），队＃外，每个点只能向右走或向下走，并且可以反复经过一个点。如今请求得最多可以获得多大好处 。
一开始看到这个题，会以为是费用流。但是计划上是在tarjan上的。我觉得如果比赛的时候有这道题估计我也就挂了。
因为这个图大部分的点只有两个后续节点， 但是*会有更多的节点，所以说这样会产生环，因此可以吧整个图求强连通进行缩点，因为每个强连通分量重的点你是可以得到她所有的值。不管走几次，就是那么多，缩完点之后就可以构成DAG这样，就能够求出从belong[1]出发得到的最远的点。一开始逗比了，忘了出发点是左上角，而且dis的赋初值写错了。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <stack>
#define loop(s,i,n) for(i = s;i < n;i++)
#define cl(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn = ;
struct edge
{
int u,v,val,next;
}; char map[][];
int dfn[maxn],low[maxn],belong[maxn],inst[maxn];
int head[maxn];
vector<edge>edges,es;
int ihead[maxn];
stack<int> st;
int vis[maxn],dis[maxn];
int dfsclock,scc,cnt;
vector<int>trans;
void init(int n)
{
int i;
loop(,i,n+)
head[i] = -; edges.clear();
es.clear();
dfsclock = scc = cnt = ;
trans.clear();
return ;
}
void addedge(int u,int v,int val)
{
int m;
struct edge e;
e.u = u;
e.v = v;
e.next = head[u];
edges.push_back(e);
m = edges.size();
head[u] = m-;
return ;
}
void tarjan(int i)
{
dfn[i] = low[i] = ++dfsclock;
inst[i] = ;
st.push(i); int j;
edge e;
for(j = head[i]; j != -; j = e.next)
{ e = edges[j];
int v;
v = e.v;
if(!dfn[v])
{
tarjan(v);
low[i] = min(low[v],low[i]);
}
else if(inst[v] && dfn[v] < low[i])
low[i] = dfn[v];
} if(dfn[i] == low[i])
{
scc++;
do
{
j = st.top();
st.pop();
inst[j] = ;
belong[j] = scc;
}
while(i != j);
}
}
void tarjans(int n)
{
dfsclock = scc = ;
memset(dfn,,sizeof(dfn));
while(!st.empty())st.pop(); cl(inst,);
cl(belong,);
int i;
loop(,i,n+)
{
if(!dfn[i]) tarjan(i);
}
return ;
}
int spfa(int s,int n)
{
int i,j;
dis[s] = ;
queue<int>q;
q.push(s);
vis[s] = ;
while(!q.empty())
{
int x;
x = q.front(); q.pop();
vis[x] = ;
struct edge e;
for(i = ihead[x]; i != -; i = e.next)
{
int v; e = es[i];
v = e.v;
if(dis[v] < dis[x]+e.val)
{
dis[v] = dis[x]+e.val;
q.push(v);
vis[v] = ;
}
}
}
int max = ;
for(i = ; i <= n; i++)
{
if(dis[i] > max)
max = dis[i];
} return max;
}
int val[maxn];
int main()
{
int t;
int n,m,k;
scanf("%d",&t);
while(t--)
{
int i,j;
int p;
p = ;
scanf("%d %d",&n,&m);
init(n*m+);
loop(,i,n)
scanf("%s",map[i]);
int leap = ;
for(i = ; i < n; i++)
{
for(j = ; j < m; j++)
{
if(map[i][j] == '*')
trans.push_back(i*m+j+);
}
} loop(,i,trans.size())
{
int l,r;
scanf("%d %d",&l,&r);
if(map[l][r] == '*')
addedge(trans[i],l*m+r+,);
else if(map[l][r] != '#')
addedge(trans[i],l*m+r+,map[l][r]-'');
} loop(,i,n)
{
loop(,j,m)
{
if(map[i][j] != '#')
{ if(i+ < n && map[i+][j] == '*')
addedge(i*m+j+,(+i)*m+j+,);
else if(i+ < n && map[i+][j] != '#')
addedge(i*m+j+,(+i)*m+j+,+map[i+][j]-''); if(j+ < m && map[i][j+] == '*' )
addedge(i*m+j+,(i)*m++j,);
else if( j+ < m && map[i][j+] != '#')
addedge(i*m+j+,i*m+j+,map[i][j+]-'');
}
}
} tarjans(m*n);
// cout<<scc<<endl;
cl(val,); int sum;
sum = ;
cl(vis,);
memset(ihead,-,sizeof(ihead));
for(i = ; i <= m*n; i++)
{
int r,l;
r = (i-)/m;
l = (i-)%m;
if(map[r][l] != '#' && map[r][l] != '*')
val[belong[i]] += map[r][l] - '';
} for(i = ; i < edges.size(); i++)
{
int u,v;
u = edges[i].u;
v = edges[i].v;
if(belong[u] != belong[v])
{
u = belong[u];
v = belong[v];
struct edge e;
e.u = u;
e.v = v;
e.val = val[v];
e.next = ihead[u];
es.push_back(e);
int m;
m = es.size();
ihead[u] = m-;
}
} cl(vis,);
cl(dis,-);
int ans; if(scc == )
printf("%d\n",val[belong[]]);
else
{
ans = ;
int ansi;
ans = spfa(belong[],scc);
printf("%d\n",ans+val[belong[]]);
} }
return ;
}