洛谷 P3387 【模板】缩点

偏执的太偏执、 2021-11-10 02:28 372阅读 0赞

## 洛谷 P3387 【模板】缩点 ##

### Description ###

*  给定一个n个点m条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
    
    允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

### Input ###

*  第一行，n,m
    
    第二行，n个整数，依次代表点权
    
    第三至m+2行，每行两个整数u,v，表示u->v有一条有向边

### Output ###

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

### Sample Input ###

> 2 2  
> 1 1  
> 1 2  
> 2 1

### Sample Output ###

> 2

### Data Size ###

*  n<=10^4,m<=10^5,0<=点权<=1000

### 题解： ###

*  一道tarjan模板
 *  思路就是用缩点转换成DAG跑dp
 *  我的代码太冗长了
 *  关于tarjan博客：[链接][Link 1]

#include <iostream> #include <cstdio> #include <stack> #include <queue> #include <cstring> #define maxn 100005 using namespace std; struct Obj {int w, num;} obj[maxn]; struct E {int next, to;} e[maxn], edge[maxn]; int n, m, num, dex, tot, num_edge, ans; int h[maxn], dfn[maxn], low[maxn], val[maxn], belong[maxn], head[maxn]; int uu[maxn], vv[maxn], in[maxn], seq[maxn], dp[maxn]; bool vis[maxn]; stack<int> stk; int read() { int x = 0; char c = getchar(); while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();} return x; } void add(int u, int v) { e[++num].next = h[u]; e[num].to = v; h[u] = num; } void tarjan(int x) { dfn[x] = low[x] = ++dex; stk.push(x), vis[x] = 1; for(int i = h[x]; i != 0; i = e[i].next) { int now = e[i].to; if(!dfn[now]) tarjan(now), low[x] = min(low[now], low[x]); else if(vis[now]) low[x] = min(low[x], dfn[now]); } if(low[x] == dfn[x]) { tot++, obj[tot].num = tot; while(1) { int now = stk.top(); obj[tot].w += val[now]; belong[now] = tot; stk.pop(); if(now == x) break; } } } void add_edge(int from, int to) { edge[++num_edge].next = head[from]; edge[num_edge].to = to; head[from] = num_edge; } void topsort() { queue<int> que; for(int i = 1; i <= tot; i++) if(!in[i]) que.push(i), dp[i] = obj[i].w; while(!que.empty()) { int now = que.front(); ans = max(ans, dp[now]); que.pop(); for(int i = head[now]; i != 0; i = edge[i].next) { dp[edge[i].to] = max(dp[edge[i].to], dp[now] + obj[edge[i].to].w); in[edge[i].to]--; if(!in[edge[i].to]) que.push(edge[i].to); } } } int main() { cin >> n >> m; for(int i = 1; i <= n; i++) val[i] = read(); for(int i = 1; i <= m; i++) { int u = read(), v = read(); uu[i] = u, vv[i] = v; add(u, v); } for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i); for(int i = 1; i <= m; i++) if(belong[uu[i]] != belong[vv[i]]) add_edge(belong[uu[i]], belong[vv[i]]), in[belong[vv[i]]]++; topsort(); cout << ans; return 0; }

转载于:https://www.cnblogs.com/BigYellowDog/p/11205289.html

[Link 1]: https://blog.csdn.net/qq_34374664/article/details/77488976