专栏首页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;
}  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [LightOJ-1356] Prime Independence 二分图+素数分解

    数据大,需要用优化的二分图,对每个数求出素因数,不独立的两个数之间就差一个素因数,若 a 去掉这个素因数得到b

    用户2965768
  • 区间更新与点值

    用户2965768
  • HDU 3018 Ant Trip(欧拉回路)

    #include <bits/stdc++.h> using namespace std; const int N=100005; int f[N]; ...

    用户2965768
  • 最大连续子序列和(最大子数组和)四种最详细的解法

    解法1:穷举暴力法 枚举左端点跟右端点,然后遍历更新所有的子序列和,最终得到结果就是最大的

    用户7727433
  • 不引入新的数组,实现数组元素交换位置函数

             最近遇到一道C++的面试题,要求不引入新的数组,实现数组元素交换位置函数,看似挺简单的,却还是花费了我不少时间,这里记录下来,给大家一个简单的...

    用户1221057
  • A+B Problem(V)

    做了A+B Problem之后,Yougth感觉太简单了,于是他想让你求出两个数反转后相加的值。帮帮他吧

    书童小二
  • 图论建图

    图论建图无外乎邻接表建图和链式前向星建图,不要问我是怎么知道的,要是你的学校逼你打图论位的话你就知道了。

    ACM算法日常
  • Day2上午解题报告

    预计分数:100+0+60=160 实际分数:100+0+60=160 mmpT1数据错了。。。 T1遭遇 题目描述 你是能看到第一题的 friends呢。 —...

    attack
  • c语言之函数指针和指针函数的区别

    函数指针:是指向函数的指针变量,因而函数指针本身应该是指针变量,只不过指针变量指向函数。

    绝命生
  • c++之初始化列表

    绝命生

扫码关注云+社区

领取腾讯云代金券