博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
UVA 11324 The Largest Clique(强连通分量+缩点DAG的DP)
阅读量:5865 次
发布时间:2019-06-19

本文共 1933 字,大约阅读时间需要 6 分钟。

题意:给定一个有向图,求出一个最大的结点集,这个节点集中的随意两个点之间至少一个能到达还有一个点。

思路:假设一个点在这个节点集中,那么它所在的强连通分量中的点一定所有在这个节点集中,反之亦然,

求出强连通分量并缩点,每一个新点有一个权值即这个强连通分量中点的个数,在DAG上DP就可以。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-6#define LL long long#define pii (pair
)//#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;const int maxn = 2000;const int INF = 0x3f3f3f3f;//强连通分量int n, m, w[maxn];vector
G[maxn];int pre[maxn], lowlink[maxn], sccno[maxn], dfs_clock, scc_cnt;stack
S;void dfs(int u) { pre[u] = lowlink[u] = ++dfs_clock; S.push(u); for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if(!pre[v]) { dfs(v); lowlink[u] = min(lowlink[u], lowlink[v]); } 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; w[scc_cnt]++; if(x == u) break; } }}void find_scc(int n) { dfs_clock = scc_cnt = 0; memset(sccno, 0, sizeof(sccno)); memset(pre, 0, sizeof(pre)); memset(w, 0, sizeof(w)); for(int i = 1; i <= n; i++) if(!pre[i]) dfs(i);}vector
G2[maxn];int d[maxn];int dp(int cur) { if(d[cur] != -1) return d[cur]; int ans = w[cur]; for(int i = 0; i < G2[cur].size(); i++) { ans = max(ans, w[cur]+dp(G2[cur][i])); } return d[cur] = ans;}int main() { //freopen("input.txt", "r", stdin); int T; cin >> T; while(T--) { cin >> n >> m; for(int i = 1; i <= n; i++) G[i].clear(), G2[i].clear(); for(int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); G[u].push_back(v); } find_scc(n); for(int i = 1; i <= n; i++) { for(int j = 0; j < G[i].size(); j++) { if(sccno[i] != sccno[G[i][j]]) G2[sccno[i]].push_back(sccno[G[i][j]]); } } memset(d, -1, sizeof(d)); int ans = 0; for(int i = 1; i <= scc_cnt; i++) { ans = max(ans, dp(i)); } cout << ans << endl; } return 0;}

转载地址:http://dvynx.baihongyu.com/

你可能感兴趣的文章
简单四则运算及表达式校验
查看>>
一次Linux、Tomcat和Oracle数据库优化过程
查看>>
Vue 2.0 入门系列(5)组件实例之任务列表
查看>>
史上最全的微信小程序开发解决方案
查看>>
利用Laravel 搭建oauth2 API接口 附 Unauthenticated 解决办法
查看>>
Android四大组件之Activity
查看>>
PHP正则表达式
查看>>
剑指offer中的算法题(PHP版)
查看>>
Yaconf – 一个高性能的配置管理扩展
查看>>
当Node.js遇见Docker
查看>>
webpack与browser-sync热更新原理深度讲解
查看>>
android ijkplayer c层分析-渲染显示线程
查看>>
蓝绿部署、A/B测试以及灰度发布
查看>>
PHP 7.1 源代码学习:ubuntu 环境下载,编译源代码
查看>>
百度成立国内首个深度学习教育联盟,将制定行业标准
查看>>
《Using Docker》书评和与作者Adrian Mouat的问答
查看>>
dotTrace 6.1帮你理解SQL查询如何影响应用性能
查看>>
Propel: 由Node.js之父创建的JavaScript科学计算库
查看>>
Elixir 1.2带来多项功能增强和性能提升
查看>>
如何使用 Druid 和 Kafka 构造 Kappa 架构完成流量分析
查看>>