[luogu P5960] 【模板】差分约束算法-爱代码爱编程
题目
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