有向图缩点(强连通分量)
发布日期:2021-06-27 21:40:32
浏览次数:1
分类:技术文章
本文共 1642 字,大约阅读时间需要 5 分钟。
有向图缩点
解题思路
这题先求强连通分量缩点
再进行dpAC代码
#include#include #include using namespace std;int n,m,T,TT,tot,tot1,top,ans; int f[10005],ru[10005],dfn[10005],low[10005],col[10005],sum[10005],num[10005],stak[10005],head[10005],head1[10005];struct node{ int to,next;}a[100005],b[100005];void add(int x,int y){ a[++tot]=(node){ y,head[x]}; head[x]=tot;}void add1(int x,int y){ b[++tot1]=(node){ y,head1[x]}; head1[x]=tot1;}void Tarjan(int x)//求强连通分量缩点{ dfn[x]=low[x]=++T; stak[++top]=x; for(int i=head[x];i;i=a[i].next) { int v=a[i].to; if(!dfn[v]) { Tarjan(v); low[x]=min(low[x],low[v]); } else if(!col[v])low[x]=min(low[x],low[v]); } if(dfn[x]==low[x]) { col[x]=++TT; sum[TT]=num[x]; while(stak[top]!=x) sum[TT]+=num[stak[top]],col[stak[top--]]=TT; top--; } return;}void dp(){ queue q;//队列 for(int i=1;i<=tot;i++)if(!ru[i])q.push(i),f[i]=sum[i]; while(!q.empty()) { int x=q.front(); q.pop(); for(int i=head1[x];i;i=b[i].next) { int v=b[i].to; f[v]=max(f[v],f[x]+sum[v]);//用点u更新点v的f值 ru[v]--; if(!ru[v])q.push(v); } } return;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&num[i]); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); add(x,y); } for(int i=1;i<=n;i++) if(!dfn[i])Tarjan(i); for(int i=1;i<=n;i++) for(int j=head[i];j;j=a[j].next)//枚举原图的所有边 { int v=a[j].to; if(col[i]!=col[v])//判断是否来自不同的强连通分量 { add1(col[i],col[v]);//在新图中从点col[i]向col[v]连一条边 ru[col[v]]++;//col[v]入度++ } } dp(); for(int i=1;i<=n;i++) ans=max(ans,f[i]); printf("%d",ans); return 0;}
谢谢
转载地址:https://blog.csdn.net/weixin_45524309/article/details/117473514 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年02月28日 19时10分24秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
c++ jna 数据类型_JNA 使用总结
2019-04-21
python中如何遍历列表并将列表值赋予_python中如何实现遍历整个列表?
2019-04-21
java clone equals_(原)java中对象复制、==、equals
2019-04-21
计算机二级java技巧,计算机二级报java难考吗
2019-04-21
拉格朗日matlab编程例题,Matlab习题讲解.doc
2019-04-21
case是不是php语言关键字,PHP语言 switch 的一个注意点
2019-04-21
linux php mkdir失败,linux – mkdir错误:参数无效
2019-04-21
config.php渗透,phpMyAdmin 渗透利用总结
2019-04-21
android开发的取消清空按钮,Android开发实现带清空按钮的EditText示例
2019-04-21
mysql整体会滚_滚mysql
2019-04-21
向mysql数据库中添加批量数据类型_使用JDBC在MySQL数据库中快速批量插入数据
2019-04-21
mssql连接mysql数据库文件_在本地 怎么远程连接MSSQL数据库
2019-04-21
mssql 远程无法连接mysql_解决SQLServer远程连接失败的问题
2019-04-21