代码编织梦想

题目

https://www.luogu.com.cn/problem/P5960


code

#include<cstdio>
#include<cstring>
using namespace std;
const int inf=21474836; 
const int inn=50001;  
struct node{ int y,w,next; }a[inn];
int n,m,len,f[inn],last[inn]; bool b[inn]; 
void add(int x,int y,int z){a[++len]=(node){y,z,last[x]}; last[x]=len;}
bool spfa(int k){
	b[k]=1; 
	for(int i=last[k];i;i=a[i].next){
		int y=a[i].y; 
		if (f[y]<f[k]+a[i].w) {
			f[y]=f[k]+a[i].w; 
			if (b[y]) return 0; 
			if (!spfa(y)) return 0; 
		} 
	}
	b[k]=0; 
	return 1; 	
}
int main(){
	memset(f,0,sizeof(f)); 
	scanf("%d%d",&n,&m); 
	int x,y,z; 
    for(register int i=1;i<=m;i++)
	  scanf("%d%d%d",&x,&y,&z),add(x,y,-z); 
	for(register int i=1;i<=n;i++) f[i]=-inf,add(0,i,0); 
	if (!spfa(0)) printf("NO"); else {
		for(register int i=1;i<=n;i++) printf("%d ",f[i]);
	}
	return 0; 
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接: https://blog.csdn.net/qq_39897867/article/details/107744087

Codeforces E Post Lamps-爱代码爱编程

E Post Lamps  思路: 条件:照亮[0,n]段,选一种灯泡订购,灯泡有价格和向后照射长度,设置了不能放置的位置 1、计算可以选择的最短长度,因为有blocked,因此必须从其前一格放置灯,并且覆盖blocked区域。 计算blocked 的方法: (1) [0,1,2,3,4,5,6]  3,4,5 不能用,必须选择长度大于等于[2,

【剑指offer】面试题67:把字符串转换成整数-爱代码爱编程

67. 把字符串转换成整数 写一个函数 StrToInt,实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。 首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。 当我们寻找到的第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字组合起来,作为该整数的正负号;假如第一个非空字符是数字,

NOI题库1.3答案-爱代码爱编程

第一题 A+B问题 #include<iostream> using namespace std; int main() {     int a,b,c;     cin>>a>>b;     c=a+b;     cout<+<c<<endl;     system("pause");    

Qt异步加载,页面显示和数据处理分离-爱代码爱编程

前面文章讲了QTableView实现表格加载百万条数据,但是数据操作是在主线程里面,如果碰到耗时的数据查询或者操作时,主线程会阻塞,就会导致页面卡主,无法响应,这样很影响用户体验。这篇文章介绍利用信号槽和多线程实现Qt异步操作,同时数据处理显示进度条。 1.实现原理 创建数据处理类CDataClass继承QObject接收页面操作创建操作类Worker

C语言 将一个字符串中的浮点数全部变为整数-爱代码爱编程

在压缩精简svg文件的路径时非常有用 //fumiama 20200802 //allFloat2Int.c #include <stdio.h> #include <string.h> #include <ctype.h> #define INPUT argv[1] int main(int argc,

leetcode_只出现一次的数字_C++代码(附思路)-爱代码爱编程

leetcode_只出现一次的数字_C++代码(附思路) 题目: 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 说明: 你的算法应该具有线性时间复杂度。 你可以 不使用额外空间来实现吗? 示例一: 输入: [2,2,1] 输出: 1 示例二: 输入: [4,1,2,

[luogu P1495] 【模板】中国剩余定理(CRT)/曹冲养猪-爱代码爱编程

题目 https://www.luogu.com.cn/problem/P1495 解题思路 信息学奥赛一本通上的。额,模板 代码 #include<iostream> using namespace std; typedef long long LL; LL a[11],b[11],N,M=1,Ans=0; void Read

C++模板-爱代码爱编程

       模板定义:模板就是实现代码重用机制的一种工具,它可以实现类型参数化,即把类型定义为参数, 从而实现了真正的代码可重用性。模版可以分为两类,一个是函数模版,另外一个是类模版。 函数模板如下面的例子: int func_max(int a, int b) { return a>b?a:b; }       求两个整数的最大值,

C/C++复习之路——王道程序员求职宝典——第六章《函数》-爱代码爱编程

文章目录 参数传递形参/实参传递指针的引用内联函数默认参数函数重载函数模板与泛型 参数传递 形参/实参 形参:出现在函数定义中,在整个函数体内都可以使用,离开该函数则不能使用。实参:出现在主调函数中,进入被调函数后,是参变量也不能使用。 例。fun((exp1,exp2), (exp3,exp4,exp5))有几个实参? 解析:2个。(ex

模板特化以及模板分离操作-爱代码爱编程

一、模板特化。 (一). 函数模板的特化: 函数模板的特化步骤: 必须要先有一个基础的函数模板关键字template后面接一对空的尖括号<>函数名后跟一对尖括号,尖括号中指定需要特化的类型函数形参表: 必须要和模板函数的基础参数类型完全相同,如果不同编译器可能会报错。#include<iostream> #include<

#spfa# [luogu P3385] 【模板】负环-爱代码爱编程

Title https://www.luogu.com.cn/problem/P3385 Solution Code #include<cstdio> #include<queue> #include<cstring> using namespace std; const int inn=100001; st

一个自定义的C++线程安全的对象模板-爱代码爱编程

简介 在多线程操作中,为了避免对线程共享数据的操作冲突,一般会使用互斥锁,如 mutex。为了让结构更加合理,在本文中,作者利用模板,定义了一个通用的线程间操作安全的模板对象类。 原理 基本原理是使用模板支持不同的数据类型,然后在模板类中通过一个互斥锁,实现加锁和解锁操作,从而避免数据在多线程操作中的冲突。 具体实现代码如下所示: // Lock