递推求解DAG最长路径长度及最长路径条数
2021/9/15 23:08:36
本文主要是介绍递推求解DAG最长路径长度及最长路径条数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
说明
在一般图中,求解最长路或最短路只能通过最短路算法解决
但是在DAG中,由于不存在环,因此可以通过递推,以线性复杂度计算处最长路或最短路。当然需要首先对有向图进行Tarjan缩点转化为DAG
例题
题目理解
首先对题目中涉及到的几个概念做几点说明:
- 半连通:任意点对\((u, v)\),满足\(u->v\) 或 \(v->u\)有路径。因为且是满足或的,所以强连通满足半连通
因此若要满足半连通,只需没有孤立点即可 - 导出子图:图\(G\)的导出子图是指,\(G\)顶点的一个子集\(E\)和\(G\)中两端顶点均在\(E\)中的边构成的图
如果理解了半连通和导出子图的定义,有一定概率我们可以想到如果将原图转换为DAG,因为图上边权是一致的,因此包含最多节点数目的一条路径是最长路
如果可以想到这个结论,下一步的想法很自然的就是去判断最长路是否为最大半连通子图,有以下两点因素需要考虑:
- 最长路是否为半连通的
因为强连通是半连通的且单向链路是半连通的,而Tarjan缩点后图上最长路是一条包含强连通分量的单向链路,因此最长路是半连通的 - 最长路是否为导出子图
若最长路中的两点之间存在重边,显然最长路只会包含重边中的一条,但根据导出子图的定义,导出子图应当将该两点中的重边全部包含在内,因此最长路并非导出子图
虽然最长路并非最大半连通子图,但是可以发现,最长路不满足最大半连通子图的原因在于没有选择一些重边,假设我们加上这些重边,那么最长路显然就成为了最大半连通子图。而且我们可以发现,虽然加上了这些边,但最长路中点的数量并没有发生改变
综上所述,实际结论为:最大半连通子图拥有的节点数 $K == $ 有向有环图转换为DAG后最长路的长度,不同的最大半连通子图的数目$C == $有向有环图转换为DAG后最长路的条数
代码实现
- Tarjan求强连通分量缩点,将原图转换为DAG
- 利用DP思想递推求解最长路长度和最长路条数
f[i]: 统计走到i点时获得的最大长度
g[i]:统计以最大长度走到i点时的方案数
设i点的前驱节点有一个j,则操作逻辑如下
// 从j点走来总长度大于当前最大长度,则选择从j点走来 if (f[j] + Size[i] > f[i]) { f[i] = f[j] + Size[i]; g[i] = f[j]; } // 从j点走来总长度与当前最大长度相等,则走到i点既可以按现在的方案也可以选择从j点走来 else if (f[j] + Size[i] == f[i]) g[i] += g[j];
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <queue> #include <stack> #include <vector> #include <unordered_map> using namespace std; using LL = long long; const int N = 1e5 + 10, M = 2e6 + 10; // M应当包含原图和缩点后的图,边数应当*2 int n, m, mod; int h[N], hs[N], e[M], ne[M], idx; stack<int> stk; bool in_stk[N]; int dfn[N], low[N], timestamp; int id[N], Size[N], scc_cnt; unordered_map<LL, bool> st; int f[N], g[N]; void add(int *h, int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx ++; } void tarjan(int u) { dfn[u] = low[u] = ++ timestamp; stk.push(u); in_stk[u] = true; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (!dfn[j]) { tarjan(j); low[u] = min(low[u], low[j]); } else if (in_stk[j]) low[u] = min(low[u], dfn[j]); } if (dfn[u] == low[u]) { int y; ++ scc_cnt; do { y = stk.top(); stk.pop(); in_stk[y] = false; id[y] = scc_cnt; ++ Size[scc_cnt]; } while (y != u); } } int main() { memset(h, -1, sizeof h); memset(hs, -1, sizeof hs); cin >> n >> m >> mod; for (int i = 0; i < m; ++ i) { int a, b; cin >> a >> b; add(h, a, b); } for (int i = 1; i <= n; ++ i) if (!dfn[i]) tarjan(i); for (int i = 1; i <= n; ++ i) for (int j = h[i]; ~j; j = ne[j]) { int k = e[j]; int a = id[i], b = id[k]; LL hash = a * 1000000ll + b; // 可能会爆int,需要ll if (a != b && !st[hash]) { add(hs, a, b); st[hash] = true; } } /** * 递推需要按照拓扑序进行,否则数据无法更新完全 * scc_cnt越小,则其在拓扑序中越靠后 * scc_cnt从大到小的顺序即为拓扑序的顺序 */ for (int i = scc_cnt; i >= 1; -- i) // for (int i = 1; i <= scc_cnt; ++ i) { if (!f[i]) { f[i] = Size[i]; g[i] = 1; } for (int j = hs[i]; ~j; j = ne[j]) // 注意这里的节点是指缩点之后的节点,需要使用hs { int p = e[j]; if (f[p] < f[i] + Size[p]) { f[p] = f[i] + Size[p]; g[p] = g[i]; } else if (f[p] == f[i] + Size[p]) g[p] = (g[p] + g[i]) % mod; } } int maxf = -0x3f3f3f3f, maxg = -0x3f3f3f3f; for (int i = 1; i <= scc_cnt; ++ i) if (f[i] > maxf) { maxf = f[i]; maxg = g[i]; } else if (f[i] == maxf) maxg = (maxg + g[i]) % mod; cout << maxf << endl << maxg << endl; return 0; }
这篇关于递推求解DAG最长路径长度及最长路径条数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性