记录编号	390342	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2014] 智哥的超时空传送	最终得分	100
用户昵称	Albert S. Chang	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-04-02 19:01:36	内存使用	0.00 MiB

#include <stack>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;

const int INF=0x7FFFFFFF;
const int MAXV=2010;
const int MAXE=10010;

struct Edge{
	int from;
	int to;
	Edge* next;
};

Edge E[MAXE];
Edge* head[MAXV];//
Edge* top;//

int n;
int m;
int scc;//
int Time;//
int fans;//
int ans[MAXV];//
int dfn[MAXV];//
int low[MAXV];//
int size[MAXV];//
int value[MAXV];
int belong[MAXV];

stack<int> s;

bool inStack[MAXV];

char buf[MAXV];

void Initialize();
void Tarjan(int);
void SweepEdge();
void DFS(int,int);
void Insert(int,int);

int Main(){
#ifndef ASC_LOCAL
	freopen("tramcar.in","r",stdin);
	freopen("tramcar.out","w",stdout);
#endif

	int T;
	scanf("%d",&T);
	while(T--){
		Initialize();
		Tarjan(0);
		SweepEdge();
		DFS(belong[0],size[belong[0]]);
		printf("%d\n",fans);
	}
	return 0;
}

void DFS(int root,int sum){
	if(sum<=ans[root])
		return;
	ans[root]=sum;
	fans=max(fans,ans[root]);
	for(Edge* i=head[root];i!=NULL;i=i->next){
		DFS(i->to,sum+size[i->to]);
	}
}

void Tarjan(int root){
	Time++;
	dfn[root]=Time;
	low[root]=Time;
	s.push(root);
	inStack[root]=true;

	for(Edge* i=head[root];i!=NULL;i=i->next){
		if(dfn[i->to]==0){
			Tarjan(i->to);
			low[root]=min(low[root],low[i->to]);
		}
		else if(inStack[i->to]){
			low[root]=min(low[root],dfn[i->to]);
		}
	}

	if(low[root]==dfn[root]){
		scc++;
		int top;
		do{
			top=s.top();
			belong[top]=scc;
			size[scc]+=value[top];
			inStack[top]=false;
			s.pop();
		}while(top!=root);
	}
}

void SweepEdge(){
	Edge* topx=top;
	top=E;
	memset(head,0,sizeof(head));
	for(Edge* i=E;i!=topx;i++){
		if(belong[i->from]!=belong[i->to]&&belong[i->from]!=0){
			Insert(belong[i->from],belong[i->to]);
		}
	}
}

void Initialize(){
	memset(head,0,sizeof(head));
	memset(size,0,sizeof(size));
	memset(ans,0xFF,sizeof(ans));
	memset(low,0,sizeof(low));
	memset(dfn,0,sizeof(dfn));
	memset(belong,0,sizeof(belong));
	top=E;
	scc=0;
	Time=0;
	fans=0;

	scanf("%d%d",&n,&m);
	int x,y;
	for(int i=0;i<n*m;i++){
		buf[i]=getchar();
		while((buf[i]<'0'||buf[i]>'9')&&buf[i]!='*'&&buf[i]!='#'){
			buf[i]=getchar();
		}
	}

	for(int i=0;i<n*m;i++){
		if(buf[i]!='#'){
			if(i>=m&&buf[i-m]!='#'){
				Insert(i-m,i);
			}
			if(i%m!=0&&buf[i-1]!='#'){
				Insert(i-1,i);
			}
			if(buf[i]=='*'){
				scanf("%d%d",&x,&y);
				if(buf[x*m+y]!='#')
					Insert(i,x*m+y);
				value[i]=0;
			}
			else{
				value[i]=buf[i]-'0';
			}
		}
	}
}

inline void Insert(int from,int to){
	top->from=from;
	top->to=to;
	top->next=head[from];
	head[from]=top;
	top++;
}

int WORKING=Main();
int main(){;}