有向图缩点(强连通分量)
发布日期:2021-06-27 21:40:32 浏览次数:1 分类:技术文章

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

有向图缩点

在这里插入图片描述

解题思路

这题先求强连通分量缩点

进行dp

AC代码

#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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:受欢迎的牛(强连通分量)
下一篇:P4009 汽车加油行驶问题(spfa)

发表评论

最新留言

第一次来,支持一个
[***.219.124.196]2024年02月28日 19时10分24秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

c++ jna 数据类型_JNA 使用总结 2019-04-21
python中如何遍历列表并将列表值赋予_python中如何实现遍历整个列表? 2019-04-21
apache php mysql架构图_Apache+PHP+MYSQL+Tomcat+JK架构设计技巧与应用实战 2019-04-21
java clone equals_(原)java中对象复制、==、equals 2019-04-21
php7 memcached.exe,PHP7 下安装 memcache 和 memcached 扩展 2019-04-21
计算机二级java技巧,计算机二级报java难考吗 2019-04-21
php foreach 数据库,php – 使用foreach将数据库检索的数据排列在HTML表中 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
java list 合并 重复的数据_Java ArrayList合并并删除重复数据3种方法 2019-04-21
android volley 上传图片 和参数,android - 使用android中的volley将图像上传到multipart中的服务器 - 堆栈内存溢出... 2019-04-21
android开发的取消清空按钮,Android开发实现带清空按钮的EditText示例 2019-04-21
android gp服务,ArcGIS Runtime SDK for Android开发之调用GP服务(异步调用) 2019-04-21
mysql整体会滚_滚mysql 2019-04-21
向mysql数据库中添加批量数据类型_使用JDBC在MySQL数据库中快速批量插入数据 2019-04-21
最全的mysql 5.7.13_最全的mysql 5.7.13 安装配置方法图文教程(linux) 强烈推荐! 2019-04-21
mssql连接mysql数据库文件_在本地 怎么远程连接MSSQL数据库 2019-04-21
mssql 远程无法连接mysql_解决SQLServer远程连接失败的问题 2019-04-21