当前位置: 代码迷 >> 综合 >> poj 3592 Instantaneous Transference 强连通缩点+在DAG上dp求最长路
  详细解决方案

poj 3592 Instantaneous Transference 强连通缩点+在DAG上dp求最长路

热度:78   发布时间:2024-01-19 06:12:48.0

题意:

给一个地图,在每一点只能向下或向右走,其中标有‘*’点上有传送门可以传送到他指定的位置,标有数字的点上代表在该点可以得到的矿石,标有‘#’的点代表这点不能走,求从(0,0)点开始能最多获得多少矿石。

分析:

因为有传送门所以图中可能有环,缩点后在所得的DAG中求最长路就可以了。

代码:

//poj 3592
//sep9
#include <iostream>
#include <vector>
using namespace std;
const int maxN=64;
char g[maxN][maxN];
int map[maxN][maxN];
int vis[maxN*maxN],dfn[maxN*maxN],sum[maxN*maxN],dp[maxN*maxN];
int n,N,M,cnt,scc;
vector<int> graph[maxN*maxN],ngraph[maxN*maxN],dag[maxN*maxN];void addegde(int u,int v)
{graph[u].push_back(v);ngraph[v].push_back(u);		
}void dfs(int k)
{vis[k]=1;for(int i=graph[k].size()-1;i>=0;--i)if(!vis[graph[k][i]])dfs(graph[k][i]);dfn[++cnt]=k;
}void ndfs(int k)
{vis[k]=scc;for(int i=ngraph[k].size()-1;i>=0;--i)if(!vis[ngraph[k][i]])ndfs(ngraph[k][i]);	
}void kosaraju()
{memset(vis,0,sizeof(vis));cnt=0;for(int i=0;i<n;++i)if(!vis[i])dfs(i);	memset(vis,0,sizeof(vis));scc=0;for(int i=n;i>=1;--i)if(!vis[dfn[i]]){++scc;ndfs(dfn[i]);}
}void search(int u)
{if(dp[u]!=-1)return ;else{int maxx=0;for(int i=dag[u].size()-1;i>=0;--i){int v=dag[u][i];search(v);maxx=max(maxx,dp[v]);}dp[u]=maxx+sum[u];}return ;	
}int main()
{int cases,i,j;scanf("%d",&cases);while(cases--){scanf("%d%d",&N,&M);	n=N*M;for(i=0;i<=N;++i)for(j=0;j<=M;++j)map[i][j]=i*M+j;		for(i=0;i<N;++i)scanf("%s",g[i]);for(i=0;i<=n;++i)graph[i].clear(),ngraph[i].clear(),dag[i].clear();for(i=0;i<N;++i)for(j=0;j<M;++j){		if(g[i][j]!='#'){if(i+1<N&&g[i+1][j]!='#')addegde(map[i][j],map[i+1][j]);if(j+1<M&&g[i][j+1]!='#')addegde(map[i][j],map[i][j+1]);if(g[i][j]=='*'){int r,c;scanf("%d%d",&r,&c);if(g[r][c]!='#')addegde(map[i][j],map[r][c]);}}}				kosaraju();for(i=0;i<n;++i)for(j=graph[i].size()-1;j>=0;--j){int u=i,v=graph[i][j];if(vis[u]!=vis[v])dag[vis[u]].push_back(vis[v]);}memset(sum,0,sizeof(sum));for(i=0;i<N;++i)for(j=0;j<M;++j)if(g[i][j]<='9'&&g[i][j]>='0'){int p=map[i][j];sum[vis[p]]+=g[i][j]-'0';}int start=vis[map[0][0]];			memset(dp,-1,sizeof(dp));search(start);	printf("%d\n",dp[start]);}return 0;	
}