http://poj.org/problem?id=3592
题意 ：给你一个n*m的矩阵，每个位置上都有一个字符，如果是数字代表这个地方有该数量的金矿，如果是*代表这个地方有传送带并且没有金矿，可以传送到指定的位置，如果是#代表该位置不可走，初始位置在左上角，只能向下或向右走，并且走到传送带的时候可选择是否传送。问当走出去的时候能获得的最大近况数是多少。
思路 ：先将二维矩阵转化成一维的点建图，可以向下向右建图，而且传送带也可以建边，缩点之后再建边，最后用spfa求最长路。
#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h> using namespace std; const int maxn = ;
const int INF = - ; int belong[maxn],instack[maxn],dfn[maxn],low[maxn],g[maxn],map[maxn],c[maxn] ;
//belong[i]指的是i点所在的联通分量的编号。instack模拟的是栈，因为每个节点是要入栈的，来判断是否属于同一个分量
//dfn[i]为搜索i结点的次序编号，Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。
//g[i]是指将一个矩阵从0到n*m编号之后的，i点所在的那个位置的宝藏数，map[i]记录的是第i个传送带的位置
//c[i]记录的是第i个联通分量中宝藏的总数。
int cntt,cnt,top,bcc_clock,cntb,n,m,num ;
int head1[maxn] ,head[maxn];
char point[][] ;//输入的地图
int dis[maxn],coun[maxn],index ;
bool vis[maxn],flag[maxn] ;
int dire[][] = {{,},{,}} ; struct node
{
int u,v,w,next ;
} p[maxn] ,ch[maxn]; void addedge(int u,int v)
{
p[cnt].u = u ;
p[cnt].v = v ;
p[cnt].next = head[u] ;
head[u] = cnt++ ;
} void addnode(int u,int v,int w)
{
ch[cntt].u = u ;
ch[cntt].v = v ;
ch[cntt].w = w ;
ch[cntt].next = head1[u] ;
head1[u] = cntt++ ;
} void tarjan(int u)
{
vis[u] = true ;
dfn[u] = low[u] = ++bcc_clock ;
instack[++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])
{
cntb++ ;
int v ;
do
{
v = instack[top--] ;
vis[v] = false ;
belong[v] = cntb ;
}
while(v != u) ;
}
} void Init()
{
memset(dfn,,sizeof(dfn)) ;
memset(low,,sizeof(low)) ;
memset(belong,,sizeof(belong)) ;
memset(c,,sizeof(c)) ;
memset(vis,,sizeof(vis)) ;
num = ;
memset(head,-,sizeof(head)) ;
memset(head1,-,sizeof(head1)) ;
cnt = ,top = ,cntb = ,bcc_clock = ,cntt = ;
} bool relax(int u,int v,int w)
{
if(dis[v] < dis[u] + w)
{
dis[v] = dis[u] + w ;
return true ;
}
return false ;
} bool spfa(int u)
{
memset(flag,false,sizeof(flag)) ;
memset(coun,,sizeof(coun)) ;
flag[u] = true ;
for(int i = ; i <= cntb ; i++)
dis[i] = INF ;
queue<int >Q ;
Q.push(u) ;
dis[u] = ;
while(!Q.empty ())
{
int st = Q.front() ;
Q.pop() ;
flag[st] = false ;
for(int i = head1[st] ; i+ ; i = ch[i].next)
{
if(relax(st,ch[i].v,ch[i].w) && !flag[ch[i].v])
{
if((++coun[ch[i].v]) > m*n) return false ;
Q.push(ch[i].v) ;
flag[ch[i].v] = true ;
}
}
}
index = ;
for(int i = ; i <= cntb ; i++)
index = max(index,dis[i]) ;
return true ;
}
int main()
{
int T ;
scanf("%d",&T) ;
while(T--)
{
scanf("%d %d",&n,&m) ;
int cnnt = ;//记录传送带的个数
Init() ;
getchar() ;
for(int i = ; i < n ; i++)
scanf("%s",point[i]) ;
for(int i = ; i < n ; i++)
{
for(int j = ; j < m ; j++)
{
int k = i*m+j ;
if(point[i][j] == '#')
{
g[k] = - ;
continue ;
}
else
{
if(point[i][j] == '*')
{
map[cnnt++] = k ;
g[k] = ;
}
else if(point[i][j] >= '' && point[i][j] <= '')
g[k] = point[i][j] - '' ;
for(int ii = ; ii < ; ii++)
{
int xx = i+dire[ii][] ;
int yy = j+dire[ii][] ;
if(xx < n && yy < m)
{
if(point[xx][yy] != '#')
addedge(k,xx*m+yy) ;
}
}
}
}
}
for(int i = ; i < cnnt ; i++)
{
int x,y ;
scanf("%d %d",&x,&y) ;
if(point[x][y] != '#')
addedge(map[i],x*m+y) ;
}
// Init() ;
for(int i = ; i < n*m ; i++)
if(!dfn[i]) tarjan(i) ;
for(int i = ; i < n*m ; i++)
c[belong[i]] += g[i] ;
addnode(,belong[],c[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],c[belong[v]]) ;//两个点不属于同一个联通分量
}
}
}
spfa() ;//求最长路
printf("%d\n",index) ;
} return ;
}