poj 3592 Instantaneous Transference(tarjan+縮点+最長路)

http://poj.org/problem?id=3592
題意:n*m格子の有向図が与えられ、各格子には数字、'#'または'*'、数字は格子上の鉱石の数を表し、'#'は格子が歩けないことを表し、'*'は伝送アレイを表し、ある所定の座標に送られる.トロッコは毎回下に行くか右に1段しか歩けない.トロッコは左上から出発して、最後にどれだけの鉱石を得ることができるかを聞いた.
構想:トロッコは毎回右か下に1格しか歩けないので、これが方向図であることを説明して、最後に最も多くどれだけの鉱石を得るかを聞いて、最も長い道を求める問題であることを説明します.
図を建てる時、数字はその下と右に辺を建てる必要があります.'*'はその下、右と指定座標に辺を建てる必要がありますが、'#'は不通を表し、辺を建てる必要はありません.
ここでは、伝送アレイの存在により、ある所定の座標に到達することができ、リングの出現、すなわち強い連通成分をもたらす可能性があるため、各強い連通成分に対して点を縮める必要がある.この点の重み値は、強い連通成分のすべての点の重み値の和であり、最後に有向無ループ図を形成し、この有向無ループ図に対して最長の道を求める.
注意:最長路を求める場合、始点は(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
",ans);

	}
	return 0;
}