POJ 3160 求有向图(点权)遍历的最大权值 强连通缩点+最长路

Tags: c++

题意:

给定n个点 m条有向边的图

每个点的点权

问:

遍历一遍图能得到的最大点权(对于经过的点,可以选择是否获得该点点权,但每个点只能被获得一次)

起点可以任意。

思路:

我们把有向图缩点为有向的缩点树,则某一强连通块的权值就是该连通块下的 所有正点权值和

这样我们就可以得到一个有向无环图,显然我们选择的起点是入度为0 的点,因为所有入度不为0的点 都能从别的点走过来。

因此我们建立虚根连接所有入度为0的点,然后跑一遍最长路spfa。

#include
#include
#include
#include
#include
using namespace std;
#define inf 1000000
#define N 30100
//N为点数
#define M 150100
//M为边数
int n, m, a[N], val[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 ; 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 du[N];
void suodian(){
	memset(val, 0, sizeof(val));
	for(int i = 1; i 0)val[i] += a[bcc[i][j]];
	memset(du, 0, sizeof(du));

	for(int i = 1; i q;
	G[0].clear();
	q.push(0);
	D[0] = 0;	val[0] = 0;
	for(int i = 1; i 

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