http://poj.org/problem?id=3592
题意：给定一个n*m格子的有向图，每个格子上是数字，‘#’或 ‘*‘ ,数字代表该格子上的矿石数目，‘#‘代表该格子不能走，‘ * ‘代表一个传送阵，送往某个给定的坐标。每次矿车只能向下或向右走一格。问矿车从左上角出发，最后能最多得到多少矿石。
思路：因为矿车每次只能向右或向下走一格，说明这是这是一个有向图，最后问最多得到多少矿石，说明是求最长路的问题。
建图时， 数字 需要向其下方和右方建边，‘ * ‘需要向其下方，右方和指定坐标建边，而‘ # ‘ 代表不通，不用建边。
在这里因为传送阵的存在，它能到达某个给定的坐标，可能会导致环的出现，即强连通分量，所以我们需要对每个强连通分量缩点，该点的权值是该强连通分量中所有点的权值之和，最后形成一个有向无环图，对这个有向无环图求最长路。
注意：求最长路时，起点是（0,0）点所在强连通分量的缩点，终点是任意位置。
‘ * ‘位置仍然要向下方和右方建边。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
const int maxm = 5000;
const int maxn = 1600;
const int INF = 0x3f3f3f3f;
struct node
{
int u,v,w;
int next;
}edge[maxm],edge2[maxm];
int cnt,cnt2,head[maxm],head2[maxm];
char map[50][50];
int n,m;
int val[maxn];
int val_sum[maxn];
int dfn[maxn],low[maxn],instack[maxn],set[maxn],dep,scc;
stack <int> st;
void add(int u, int v)
{
edge[cnt].u = u;
edge[cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt++;
}
void add2(int u, int v, int w)
{
edge2[cnt2].u = u;
edge2[cnt2].v = v;
edge2[cnt2].w = w;
edge2[cnt2].next = head2[u];
head2[u] = cnt2++;
}
void build()
{
int x,y;
memset(val,0,sizeof(val));
memset(head,-1,sizeof(head));
cnt = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
int num = i*m+j;
if(map[i][j] == ‘#‘)
val[num] = 0;
else if(map[i][j] == ‘*‘)
{
val[num] = 0;
if(i < n-1 && map[i+1][j] != ‘#‘)
add(num,num+m);
if(j < m-1 && map[i][j+1] != ‘#‘)
add(num,num+1);
scanf("%d %d",&x,&y);
if(map[x][y] != ‘#‘)
add(num,x*m+y);
}
else
{
val[num] = map[i][j]-‘0‘;
if(i < n-1 && map[i+1][j] != ‘#‘)
add(num,num+m);
if(j < m-1 && map[i][j+1] != ‘#‘)
add(num,num+1);
}
}
}
}
void init()
{
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(instack,0,sizeof(instack));
memset(val_sum,0,sizeof(val_sum));
while(!st.empty()) st.pop();
dep = 0;
scc = 0;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++dep;
instack[u] = 1;
st.push(u);
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[u],low[v]);
}
else if(instack[v])
low[u] = min(low[u],dfn[v]);
}
if(dfn[u] == low[u])
{
scc++;
while(1)
{
int tmp = st.top();
st.pop();
instack[tmp] = 0;
set[tmp] = scc;
val_sum[scc] += val[tmp];
if(tmp == u)
break;
}
}
}
void Suo()
{
for(int i = 0; i < n*m; i++)
{
if(!dfn[i])
tarjan(i);
}
memset(head2,-1,sizeof(head2));
cnt2 = 0;
for(int i = 0; i < cnt; i++)
{
int u = edge[i].u;
int v = edge[i].v;
if(set[u] != set[v])
add2(set[u],set[v],val_sum[set[v]]);
}
}
int spfa(int s)
{
queue<int>que;
int dis[maxn];
int inque[maxn];
while(!que.empty()) que.pop();
for(int i = 1; i <= scc; i++)
{
dis[i] = -INF;
inque[i] = 0;
}
que.push(s);
inque[s] = 1;
dis[s] =0;
while(!que.empty())
{
int u = que.front();
que.pop();
inque[u] = 0;
for(int i = head2[u]; i != -1; i = edge2[i].next)
{
int v = edge2[i].v;
int w = edge2[i].w;
if(dis[v] < dis[u] + w)
{
dis[v] = dis[u] + w;
if(!inque[v])
{
inque[v] = 1;
que.push(v);
}
}
}
}
int ans = -1;
for(int i = 1; i <= scc; i++)
ans = max(ans,dis[i]);
return ans+val_sum[s];
}
int main()
{
int test;
int ans;
scanf("%d",&test);
while(test--)
{
scanf("%d %d",&n,&m);
for(int i = 0; i < n; i++)
scanf("%s",map[i]);
build(); //建图
init();
Suo(); //缩点
ans = spfa(set[0]); //求最长路
printf("%d\n",ans);
}
return 0;
}