缩点+DP
给定一个n个点m条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
输入格式：
第一行，n,m
第二行，n个整数，依次代表点权
第三至m+2行，每行两个整数u,v，表示u->v有一条有向边
输出格式：
共一行，最大的点权之和。
n<=10^4,m<=10^5,|点权|<=1000 算法：Tarjan缩点+DAGdp
/* 因为今天写了Tarjan呢，就做个Tarjan缩点加dp的题目 缩点将强联通分量缩成一个点 并查集合并，重新建点的权值一条边连接的两个点 不在一个并查集里就重新建边 之后dp就是一个DAG求最大路径了 */ #include<cstdio> #include<algorithm> #include<iostream> #include<cstring> #include<queue> #define MAXN 100100 using namespace std; struct Edge{ int vi; int vj; int next; }edge[MAXN * 50]; int read() { int num = 0; char c = getchar(); while(c > '9' || c < '0')c = getchar(); while(c >= '0' && c <= '9') { num *= 10; num += c - '0'; c = getchar(); } return num; } int head[MAXN]; int dfn[MAXN]; int low[MAXN]; int father[MAXN]; int stack[MAXN]; int dp[MAXN]; bool visited[MAXN]; int quan[MAXN]; int quan2[MAXN]; int rudu[MAXN]; queue<int>q; int n,m; int cnt,now,top,ans,tot; void tarjan(int x) { dfn[x] = low[x] = ++cnt; visited[x] = true; stack[++top] = x; for(int i = head[x];i;i = edge[i].next) { int vj = edge[i].vj; if(!dfn[vj]) { tarjan(vj); low[x] = min(low[x],low[vj]); } else if(visited[vj]) { low[x] = min(low[x],dfn[vj]); } } if(low[x] == dfn[x]) { tot++; while(stack[top] != x) { father[stack[top]] = tot; quan2[tot] += quan[stack[top]]; visited[stack[top]] = false; top--; } father[stack[top]] = tot; quan2[tot] += quan[stack[top]]; visited[stack[top]] = false; top--; } } void push(int vi,int vj) { now++; edge[now].vi = vi; edge[now].vj = vj; edge[now].next = head[vi]; head[vi] = now; } int main() { n = read();m = read(); for(int i = 1;i <= n;i ++) quan[i] =read(); for(int i = 1;i <= m;i++) { int vi = read(); int vj = read(); push(vi,vj); } for(int i = 1;i <= n;i ++) if(!dfn[i]) tarjan(i); memset(head,0,sizeof(head)); for(int i = 1;i <= m;i ++) { int fa = father[edge[i].vi]; int fb = father[edge[i].vj]; if(fa != fb) { push(fa,fb); rudu[fb]++; } } for(int i = 1;i <= tot;i++) { ans = max(ans,quan2[i]); if(rudu[i] == 0) q.push(i),dp[i] += quan2[i]; } while(!q.empty()) { int op = q.front(); q.pop(); /*dp[op] += quan2[op]; ans = max(ans,dp[op]);*/ for(int i = head[op];i;i = edge[i].next) { int vj = edge[i].vj; dp[vj] = max(dp[vj],dp[op] + quan2[vj]); ans = max(ans,dp[vj]); rudu[vj]--; if(rudu[vj] == 0)q.push(vj); } } printf("%d",ans); return 0; }
转载于:https://www.cnblogs.com/luoyibujue/p/7663474.html
相关资源：垃圾分类数据集及代码