Tarjan缩点+DAG图dp

题目背景

缩点+DP

题目描述

给定一个n个点m条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

输入输出格式

输入格式：

第一行，n,m

第二行，n个整数，依次代表点权

第三至m+2行，每行两个整数u,v，表示u->v有一条有向边

输出格式：

共一行，最大的点权之和。

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

n<=10^4,m<=105,|点权|<=1000 算法：Tarjan缩点+DAGdp`

如题，DAG图dp有一个很显然的思路--拓扑排序

#include<stack>

#include<cstdio>

#include<cstring>

#include<algorithm>

const int maxn = 100007;

int vul[maxn];

struct node{

	int v,next;

}edge[maxn*5],edge1[maxn*5];

int head1[maxn],num1;

int head[maxn],num;

void add_edge(int u,int v) {

	edge[++num].v=v;edge[num].next=head[u];head[u]=num;

}

void add_edge1(int u,int v) {

	edge1[++num1].v=v;edge1[num1].next=head1[u];head1[u]=num1;

}

int n,m,cnt =0,dfn[maxn],low[maxn];bool vis[maxn];

int stack[maxn],top=0;

int vulue[maxn],sum,belong[maxn];

void tarjan(int x) {

	low[x]=dfn[x]=++cnt;stack[++top]=x;

	vis[x]=1;

	for(int i=head[x];i;i=edge[i].next) {

		int v=edge[i].v;

		if(vis[v]) {

			low[x]=std::min(low[x],dfn[v]);

		}

		else if(!dfn[v]){

			tarjan(v);

			low[x]=std::min(low[x],low[v]);

		}

	}

	if(low[x]==dfn[x]) {

		sum++;

		belong[x]=sum;

		vulue[sum]+=vul[x];

		for(;stack[top]!=x;top--) {

			belong[stack[top]]=sum;vis[stack[top]]=0;

			vulue[sum]+=vul[stack[top]];

		}

		vis[x]=0; top--;

	}

}

int rd[maxn];

int q[maxn],vull[maxn];

void top_sort(){

	int h=1,tail=0;

	for(int i=1;i<=sum;++i)

		if(rd[i]==0) vull[i]=vulue[i],q[++tail]=i;

	while(h<=tail) {

		int x=q[h++];

		for(int i=head1[x];i;i=edge1[i].next) {

			int v=edge1[i].v;

			if(rd[v]) {

				vull[v]=std::max(vull[v],vull[x]+vulue[v]);

				rd[v]--;

				if(rd[v]==0) q[++tail]=v;

			}

		}

	}

	int ans=0;

	for(int i=1;i<=sum;++i)

		ans=std::max(ans,vull[i]);

	printf("%d\n",ans);

}

int main() {

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;++i)

		scanf("%d",&vul[i]);

	for(int a,b,i=1;i<=m;++i) {

		scanf("%d%d",&a,&b);

		add_edge(a,b);

	}

	for(int i=1;i<=n;++i)

		if(!dfn[i])tarjan(i);

	for(int i=1;i<=n;++i)

		for(int j=head[i];j;j=edge[j].next) {

			int v=edge[j].v;

			if(belong[v]!=belong[i]) {

				add_edge1(belong[i],belong[v]);

				rd[belong[v]]++;

			}

		}

	top_sort();

	return 0;

}

巴特西

Tarjan缩点+DAG图dp

题目背景

题目描述

输入格式：

输出格式：

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

最新文章

热门文章

巴特西

Tarjan缩点+DAG图dp

题目背景

题目描述

输入格式：

输出格式：

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

说明

最新文章

热门文章

输入样例#1：复制

输出样例#1：复制