POJ 3592 强连通缩点+spfa最长路

Tags: c++

题意:

给定n*m的地图 (从(0,0) 开始)

#代表墙,*代表传送门(能传送到的坐标在下面依次给出),数字代表宝藏数(每次经过能且仅能取走一块宝藏)

起点在(0,0), 终点任意,且每次只能↓或→,或者传送

问:

最多能拿到多少块宝藏

思路:因为能传送,所以会出现环形路径,那么我们把能构成的环形路径的点缩点得到一个点,并把该点权值设为 环形路径内所有的点权和。

对于缩点后的图,我们把每个点权值设为父边的边权

这样跑一次spfa 最长路,最远点距离就是答案。

#include
#include
#include
#include
#include
using namespace std;
#define N 1700
//N为点数
#define M 10000
//M为边数
int n, m, a[N], val[N];
int idx(int x, int y){return x*m+y;}
char map[N][N];

struct Edge{
	int from, to, nex;
	bool sign;//是否为桥
}edge[M bcc[N]; //标号从1开始

void tarjan(int u ,int fa){  
	DFN[u] = Low[u] = ++ Time ;  
	Stack[top ++ ] = u ;  
	Instack[u] = 1 ;  

	for (int i = head[u] ; i!=-1 ; i = edge[i].nex ){  
		int v = edge[i].to ;  
		if(DFN[v] == -1)
		{  
			tarjan(v , u) ;  
			Low[u] = min(Low[u] ,Low[v]) ;
			if(DFN[u] G[N];
int dis[N], D[N][N];
int spfa(){
	memset(a, 0, sizeof(a));
	memset(dis, -1, sizeof(dis));
	queueq;
	q.push(Belong[0]);
	int ans = val[Belong[0]];
	dis[Belong[0]] = ans;
	while(!q.empty()){
		int u = q.front(); q.pop();
		a[u] = 0;
		for(int i = 0; i 


本文链接:http://www.4byte.cn/learning/58682.html