专栏首页wymP1113 杂务 拓扑

P1113 杂务 拓扑

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/qq_41603898/article/details/101923858

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const int maxn = 100000000;
int head[maxn];
int cnt;
int val[20005],in[20005];
bool book[20005];
int ans[20005];
int n,as;
struct N{
	int v,nxt;	
}edge[maxn];
void add(int u,int v){
	cnt++;
	edge[cnt].v = v;
	edge[cnt].nxt = head[u];
	head[u] = cnt;
}
queue<int> q;
void topo(){
	int v;
	while(!q.empty()){
		int top = q.front();
		q.pop();	book[top] = false;
		for(int i = head[top];i;i = edge[i].nxt){
			v = edge[i].v;
			in[v]--;
			ans[v] = max(ans[v],val[v]+ans[top]);
			as = max(as,ans[v]);
			if(in[v]==0&&(!book[v])){
				
				q.push(v);	book[v] = true;
			}	
		}
	}
}
int main()
{
	int id,w,last;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d %d",&id,&w);
		val[id] = w;
		while(scanf("%d",&last)&&last){
			add(last,id);
			in[id]++;
		}
	}
	for(int i=1;i<=n;i++){
		if(!in[i])q.push(i),book[i]=true;
		ans[i] = val[i];
	}
	topo();
	printf("%d\n",as);
	return 0;
}  
本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!
本文分享自作者个人站点/博客:https://blog.csdn.net/qq_41603898复制
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 2017.5.13阶段模拟考试

    预计分数:100+50(其实感觉自己写的对)+100 实际分数:100+0+100 P1149 火柴棒等式 题目描述 给你n根火柴棍,你可以拼出多少个形如“A+...

    attack
  • ICCV 2021 | 用于细粒度 3D 形状分割的基于持久同源的图卷积网络

    标题:Persistent Homology based Graph Convolution Network forFine-grained 3D Shape ...

    3D视觉工坊
  • Android 启动优化(一) - 有向无环图

    说到 Android 启动优化,大家第一时间可能会想到异步加载。将耗时任务放到子线程加载,等到所有加载任务加载完成之后,再进入首页。

    程序员徐公
  • 启动优化 - 有向无环图

    说到 Android 启动优化,大家第一时间可能会想到异步加载。将耗时任务放到子线程加载,等到所有加载任务加载完成之后,再进入首页。

    用户9239674
  • 【译】怎样监控与可视化微服务架构

    构建和部署分布式应用程序后,监视和可视化它至关重要,以确保软件的可靠性,可用性和预期的性能。这并不容易。

    极客人
  • 浅谈什么是图拓扑排序

      在工程实践中,一个工程项目往往由若干个子项目组成。这些子项目间往往有两种关系:   (1) 先后关系,即必须在某个项完成后才能开始实施另一个子项目。   (...

    五分钟学算法
  • 化繁为简,这波全局拓扑图相当可!

    拓扑图用来描述平台各服务之间的依赖关系,也可以理解为平台服务的整体结构。拓扑图上的每个节点表示服务组件或服务的依赖项,且节点上标注有服务的运行状态和请求信息,点...

    开源小E
  • 像Apache Storm一样简单的分布式图计算

    介绍 计算可能很复杂。对我们来说,这种复杂主要就是软件世界的人类驱动力。甚至有一个学科整个都围绕着问题解决和计算——计算机科学。 当一个人开始学习计算机科学时,...

    CSDN技术头条
  • 像Apache Storm一样简单的分布式图计算

    作者:Kobi Hikri 翻译:无阻我飞扬 摘要:本文从计算机领域的“祖师爷”艾伦·图灵提出的图灵机概念开始,介绍了图形计算的概念,并以示例介绍了apache...

    企鹅号小编
  • 图的拓扑排序的算法实现,C语言,栈,超详细版本

    拓扑排序在工程管理领域中的应用广泛,可用于判断工程能否顺利开展,即判断有向图中是否存在回路。对于一个有向图,先由键盘输入其顶点和弧的信息,采用恰当存储结构保存该...

    Java架构师必看
  • KDD20 | AM-GCN:自适应多通道图卷积网络

    题目:AM-GCN: Adaptive Multi-channel Graph Convolutional Networks

    Houye
  • 无需训练,自动扩展的视觉Transformer来了

    点击上方↑↑↑“OpenCV学堂”关注我来源:公众号 机器之心 授权 来自德克萨斯大学奥斯汀分校、悉尼科技大学和谷歌的研究者提出了一个无需训练就能自动扩展框架 ...

    OpenCV学堂
  • ICLR 2022 | 无需训练!As-ViT:自动扩展视觉Transformer

    当前 Vision Transformers (ViT)领域有两个主要的痛点:1、缺少对 ViT 进行设计和扩展的有效方法;2、训练 ViT 的计算成本比卷积网...

    Amusi
  • 无需训练,自动扩展的视觉Transformer来了

    机器之心报道 编辑:小舟 来自德克萨斯大学奥斯汀分校、悉尼科技大学和谷歌的研究者提出了一个无需训练就能自动扩展框架 As-ViT,其能以高效和有原则的方式自动发...

    机器之心
  • leetcode 周赛155 | 项目管理之拓扑排序算法

    今天看了下leetcode周赛的题目,没怎么做,第四题是一道Hard题目,看了下题意感觉要用拓扑排序,但是这道题除了依赖关系,还有一个分组的变量,导致这道题处理...

    ACM算法日常
  • storm 分布式实时计算系统介绍

    在Storm之前,进行实时处理是非常痛苦的事情: 需要维护一堆消息队列和消费者,他们构成了非常复杂的图结构。消费者进程从队列里取消息,处理完成后,去更新数据库,...

    用户5265382
  • Rainbond 5.6 版本发布,增加多种安装方式,优化拓扑图操作体验

    为了方便在单机电脑上快速安装体验Rainbond,当前版本支持通过一条命令安装和体验,现在支持的平台包括:

    Rainbond开源
  • 探寻流式计算

    静态数据:为了支持决策分析而构建的数据仓库系统,其中存放的大量历史数据就是静态数据。

    宜信技术学院

扫码关注云+社区

领取腾讯云代金券