UVA11324-- The Largest Clique(SCC+DP)
-- The DP Largest
2023-09-14 09:08:13 时间
题意:给出一张有向图,求一个结点数最大的结点集,使得该结点集中随意两个结点u和v满足:要么u能够到到v,要么v能够到达u(u和v能够互相到达)
思路:我们能够缩点,用Tarjan求出全部强连通分量,让每一个SCC的权值等于它的结点个数。因为SCC图是有一个DAG,使用DP求解。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <stack> #include <algorithm> using namespace std; const int MAXN = 1005; vector<int> g[MAXN], scc[MAXN], G[MAXN]; stack<int> s; int pre[MAXN], lowlink[MAXN], sccno[MAXN], sccnum[MAXN], dfs_clock, scc_cnt; int d[MAXN]; int n, m; int Tarjan(int u) { lowlink[u] = pre[u] = ++dfs_clock; s.push(u); for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (!pre[v]) { Tarjan(v); lowlink[u] = min(lowlink[v], lowlink[u]); } else if (!sccno[v]) { lowlink[u] = min(lowlink[u], pre[v]); } } if (lowlink[u] == pre[u]) { scc_cnt++; for (;;) { int x = s.top(); s.pop(); sccno[x] = scc_cnt; sccnum[sccno[x]]++; if (x == u) break; } } } void find_scc() { memset(pre, 0, sizeof(pre)); memset(lowlink, 0, sizeof(lowlink)); memset(sccno, 0, sizeof(sccno)); memset(sccnum, 0, sizeof(sccnum)); dfs_clock = scc_cnt = 0; for (int i = 0; i < n; i++) if (!pre[i]) Tarjan(i); } int dp(int i) { int& ans = d[i]; if (ans > 0) return ans; ans = sccnum[i]; for (int j = 0; j < G[i].size(); j++) { int v = G[i][j]; ans = max(ans, dp(v) + sccnum[i]); } return ans; } int main() { int cas; scanf("%d", &cas); while (cas--) { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) g[i].clear(); int u, v; for (int i = 0; i < m; i++) { scanf("%d%d", &u, &v); u--; v--; g[u].push_back(v); } find_scc(); memset(d, -1, sizeof(d)); memset(G, 0, sizeof(G)); for (int u = 0; u < n; u++) { for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (sccno[u] != sccno[v]) G[sccno[u]].push_back(sccno[v]); } } int ans = 0; for (int i = 1; i <= scc_cnt; i++) ans = max(ans, dp(i)); printf("%d\n", ans); } return 0; }
相关文章
- Docker方式启动tomcat,访问首页出现404错误(第二篇 -- 将修改过的容器映射成镜像)
- 《快学BigData》--Redis 总结(G)(32)
- vppinfra--字节序转换、bitops、cacheline、jmp机制
- 【gcc编译优化系列】gcc编译链接时候--specs=kernel.specs链接属性究竟是个啥?
- 多基因风险预测模型2--相关概念和软件
- Go 开发常用操作技巧--map
- 【错误记录】Flutter 编译报错 ( The parameter ‘‘ can‘t have a value of ‘null‘ because of its type, but the im )
- 【Vue-Spring跨域Bug已解决】has been blocked by CORS policy: The value of the······
- ORA-28077: The attribute specified (string) exceeds the maximum length. ORACLE 报错 故障修复 远程处理
- ORA-48409: The ADR homes exceeds the maximum number [string] ORACLE 报错 故障修复 远程处理
- ORA-48411: The trace files exceeds the maximum number [string] ORACLE 报错 故障修复 远程处理
- ORA-48463: The value buffer reached the maximum length [string] ORACLE 报错 故障修复 远程处理
- ORA-55568: The maximum query length (mql) value should be atmost string based on the current _highthreshold_undoretention setting. ORACLE 报错 故障修复 远程处理
- ORA-55569: The UNDO_RETENTION parameter value should be atmost string, the _highthreshold_undoretention setting. ORACLE 报错 故障修复 远程处理
- ORA-13605: The specified task or object string does not exist for the current user. ORACLE 报错 故障修复 远程处理
- the cloudTaking Oracle to the Cloud: The Evolution of Database Systems(oracleisin)
- 修复 Ubuntu 中 “E: The package cache file is corrupted, it has the wrong hash”
- Exploring the Depths of Linux: The Power of the l Command(linux-l)
- Exploring the Power of MongoDB: The Definitive Guide to Upgrading Arrays(mongodb更新数组)
- 第十三节--对象串行化
- javascriptasp教程第十一课--Application对象