http://poj.org/problem?id=3592
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define maxn 300000
using namespace std; const int inf=-<<;
int e,head[maxn],belong[maxn],stack1[maxn],top,dfn[maxn],low[maxn],bcc_clock,bcnt,n,m,num1[][],num,gg[maxn],point[maxn],cc[maxn],ee,head1[maxn],dis[maxn],cnt[maxn],temp;
bool vis[maxn],visi[maxn];
int dir[][]= {{,},{,}};
struct node
{
int u,v,next;
} p[maxn];
struct node1
{
int u,v,w,next;
} pp[maxn];
char g[][]; void add(int u,int v)
{
p[e].u=u;
p[e].v=v;
p[e].next=head[u];
head[u]=e++;
} void addnode(int u,int v,int w)
{
pp[ee].v=v;
pp[ee].u=u;
pp[ee].w=w;
pp[ee].next=head1[u];
head1[u]=ee++;
} void tarjan(int u)
{
vis[u]=true;
dfn[u]=low[u]=++bcc_clock;
stack1[++top]=u;
for(int i=head[u]; i!=-; i=p[i].next)
{
int v=p[i].v;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
bcnt++;
int j;
do
{
j=stack1[top--];
vis[j]=false;
belong[j]=bcnt;
}
while(j!=u);
}
} void init()
{ memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(belong,,sizeof(belong));
memset(cc,,sizeof(cc));
memset(vis,false,sizeof(vis));
} void del()
{
init();
for(int i=; i<n*m; i++)
{
if(!dfn[i])
{
tarjan(i);
}
}
} bool ralex(int u,int v,int c)
{
if(dis[v]<dis[u]+c)
{
dis[v]=dis[u]+c;
return true;
}
return false;
} bool spfa(int src)
{
memset(visi,false,sizeof(visi));
memset(cnt,,sizeof(cnt));
visi[src]=true;
for(int i=; i<=bcnt; i++)
{
dis[i]=inf;
}
queue<int>q;
q.push(src);
dis[src]=;
while(!q.empty())
{
int u=q.front();
q.pop();
visi[u]=false;
for(int i=head1[u]; i!=-; i=pp[i].next)
{
if(ralex(u,pp[i].v,pp[i].w)&&!visi[pp[i].v])
{
if((++cnt[pp[i].v])>n*m) return false;
q.push(pp[i].v);
visi[pp[i].v]=true;
}
}
}
temp=;
for(int i=; i<bcnt+; i++)
{
temp=max(temp,dis[i]);
}
return true;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
num=;
int cn=;
memset(head1,-,sizeof(head1));
memset(head,-,sizeof(head));
e=,top=,bcnt=,bcc_clock=,ee=;
getchar();
for(int i=; i<n; i++)
{
scanf("%s",g[i]);
}
for(int i=; i<n; i++)
{
for(int j=; j<m; j++)
{
int k=i*m+j;
if(g[i][j]=='#')
{
gg[k]=-;
continue;
}
else
{
if(g[i][j]=='*')
{
point[cn++]=k;
gg[k]=;
}
else if(g[i][j]>=''&&g[i][j]<='')
{
gg[k]=g[i][j]-'';
}
for(int c=; c<; c++)
{
int xx=i+dir[c][];
int yy=j+dir[c][];
if(xx<n&&yy<m)
{
if(g[xx][yy]!='#')
{
add(k,xx*m+yy);
}
}
} }
}
}
for(int i=; i<cn; i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(g[x][y]!='#')
{
add(point[i],x*m+y);
}
}
del();
for(int i=; i<n*m; i++)
{
cc[belong[i]]+=gg[i];
}
addnode(,belong[],cc[belong[]]);
for(int i=; i<n*m; i++)
{
for(int j=head[i]; j!=-; j=p[j].next)
{
int v=p[j].v;
if(belong[i]!=belong[v])
{
addnode(belong[i],belong[v],cc[belong[v]]);
}
}
}
spfa();
printf("%d\n",temp);
}
return ;
}