传送门:P3387 【模板】缩点 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
顾名思义啊,一个模板题,用tarjan算法缩点之后topo + DAGdp就可以了,写一个模板,防止自己忘记。
代码
#include <bits/stdc++.h> #define int long long #define pb push_back using namespace std; const int maxn = 1e4 + 9; int a[maxn];//点权ai vector<int> g[maxn];//存图 vector<int> G[maxn];//存缩点后的 DAG int dfn[maxn], low[maxn], col[maxn], tot = 0;//tot为强联通分量编号 int idx = 0;//idx记录dfn和low的初始值 int ind[maxn];//表示入度 //栈,用于表示有哪些子节点 int stk[maxn], top = 0; bitset<maxn> ins;//表示是否在栈中 int max_num(int tmp[],int st,int ed) { int res = 0; for(int i = st;i < ed; ++ i)res = max(res, tmp[i]); return res; } void tarjan(int x) { dfn[x] = low[x] = ++ idx; stk[++ top] = x; ins[x] = 1; for(auto& y : g[x]) { //low[y] > dfn[x]判断割边 if(!dfn[y]) //如果y没有访问过 { tarjan(y); low[x] = min(low[x], low[y]); } else if(ins[y]) //如果访问过且在栈中,说明遇到父节点了,要回溯咯 { low[x] = min(low[x], dfn[y]); } } if(dfn[x] == low[x])//遇到了一个小父亲 { tot ++;//新建一个强联通分量 while(stk[top + 1] != x)//直到小父亲也加进去了,说明加完了 { col[stk[top]] = tot; ins[stk[top --]] = 0; } } } int topo(int n) { queue<int> q; //由于变量实在太多了,就在堆里面开一下 int dp[maxn], val[maxn]; memset(dp, 0, sizeof dp); memset(val, 0, sizeof val); for(int i = 1;i <= n; ++ i)val[col[i]] += a[i]; //得到topo的起点 for(int i = 1;i <= tot; ++ i)if(!ind[i])q.push(i); while(!q.empty()) { int x = q.front();q.pop(); dp[x] = max(dp[x], val[x]); for(auto &y : G[x]) { dp[y] = max(dp[y], dp[x] + val[y]); ind[y] --; if(!ind[y])q.push(y); } } return max_num(dp, 1, tot + 1); } signed main() { ios::sync_with_stdio(0); int n, m;cin >> n >> m; for(int i = 1;i <= n; cin >> a[i ++]); // oh这糟糕的码风 vector<pair<int, int> > v;//存下点,便于加到新图中 for(int i = 1;i <= m; ++ i) { int x, y;cin >> x >> y; g[x].pb(y); v.pb({x, y}); } for(int i = 1;i <= n; ++ i)if(!dfn[i])tarjan(i); //构造出了一个有向无环图 for(auto &i : v) { int x = col[i.first], y = col[i.second]; if(x == y)continue;//自环就不连接 //如果这条边不存在就加进去 if(find(G[x].begin(), G[x].end(), y) == G[x].end()) { G[x].pb(y); ind[y] ++; } } cout << topo(n) << '\n'; return 0; }
Comments NOTHING