记录编号	290720	评测结果	WWWWEEWEWEEWWWEEWEEE
题目名称	[HZOI 2014] 智哥的超时空传送	最终得分	0
用户昵称	AntiLeaf	是否通过	未通过
代码语言	C++	运行时间	0.848 s
提交时间	2016-08-06 20:04:28	内存使用	3.24 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
const int maxn=50,maxp=maxn*maxn,maxe=maxp<<2;
struct edge{
	int to;
	edge *prev;
	edge():prev(NULL){}
}ee[maxe];
int hash(int,int);
char getfchar();
void insert(int,int);
void Tarjan(int);
int findroot(int);
void merge(int,int);
int dfs(int);
int T,n,m,len,x,y,dfn[maxn],low[maxn],tim,prt[maxp],val[maxp],f[maxp];
int tx[maxn][maxn],ty[maxn][maxn];
char a[maxn][maxn];
bool ins[maxp];
edge *last[maxp];
stack<int>v;
int main(){
#define MINE
#ifdef MINE
	freopen("tramcar.in","r",stdin);
	freopen("tramcar.out","w",stdout);
#endif
	scanf("%d",&T);
	while(T--){
		len=tim=0;
		memset(last,0,sizeof(last));
		memset(dfn,0,sizeof(dfn));
		memset(low,0,sizeof(low));
		memset(ins,0,sizeof(ins));
		memset(val,0,sizeof(val));
		memset(f,0,sizeof(f));
		memset(tx,0,sizeof(tx));
		memset(ty,0,sizeof(ty));
		v=stack<int>();
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)a[i][j]=getfchar();
		for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
			prt[hash(i,j)]=hash(i,j);
			if(a[i][j]=='*'){
				scanf("%d%d",&tx[i][j],&ty[i][j]);
				tx[i][j]++;ty[i][j]++;
				if(a[tx[i][j]][ty[i][j]]!='#')
					insert(hash(i,j),hash(tx[i][j],ty[i][j]));
			}
			if(a[i][j]>='0'&&a[i][j]<='9')val[hash(i,j)]=(int)(a[i][j]-'0');
			if(a[i][j]!='#'){
				if(i<n&&a[i+1][j]!='#')insert(hash(i,j),hash(i+1,j));
				if(j<m&&a[i][j+1]!='#')insert(hash(i,j),hash(i,j+1));
			}
		}
		Tarjan(hash(1,1));
		len=0;
		memset(last,0,sizeof(last));
		for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
			if(a[i][j]=='*'){
				if(a[tx[i][j]][ty[i][j]]!='#'&&findroot(hash(i,j)!=findroot(hash(tx[i][j],ty[i][j]))))
					insert(hash(i,j),hash(tx[i][j],ty[i][j]));
			}
			if(a[i][j]!='#'){
				if(i<n&&a[i+1][j]!='#'&&findroot(hash(i,j))!=findroot(hash(i+1,j)))
					insert(hash(i,j),hash(i+1,j));
				if(j<m&&a[i][j+1]!='#'&&findroot(hash(i,j)!=findroot(hash(i,j+1))))
					insert(hash(i,j),hash(i,j+1));
			}
		}
		printf("%d\n",dfs(hash(1,1)));
	}
	return 0;
}
inline int hash(int x,int y){
	return x*n+y;
}
char getfchar(){
	char c;
	do c=getchar();while(c!='*'&&c!='#'&&(c<'0'||c>'9'));
	return c;
}
void Tarjan(int x){
	int y;
	dfn[x]=low[x]=++tim;
	v.push(x);
	for(edge *e=last[x];e;e=e->prev){
		y=e->to;
		if(!dfn[y]){
			Tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(ins[y])low[x]=min(low[x],low[y]);
	}
	if(dfn[x]==low[x])do{
		y=v.top();
		v.pop();
		ins[y]=false;
		merge(x,y);
	}while(x!=y);
}
int findroot(int x){
	if(prt[x]!=x)prt[x]=findroot(prt[x]);
	return prt[x];
}
void merge(int x,int y){
	int rx=findroot(x),ry=findroot(y);
	if(rx==ry)return;
	val[rx]+=ry;
	prt[ry]=rx;
}
void insert(int x,int y){
	ee[len].to=y;
	ee[len].prev=last[x];
	last[x]=&ee[len++];
}
int dfs(int x){
	if(f[x])return f[x];
	int y;
	f[x]=val[x];
	for(edge *e=last[x];e;e=e->prev){
		y=e->to;
		f[x]=max(f[x],f[y]+val[x]);
	}
	return f[x];
}