[luoguP1993] 小 K 的农场(差分约束 + spfa 判断负环)

传送门文章地址https://www.yii666.com/article/756138.html

差分约束系统。。找负环用spfa就行文章来源地址https://www.yii666.com/article/756138.html网址:yii666.com

——代码网址:yii666.com<文章来源地址:https://www.yii666.com/article/756138.html

 #include <cstdio>
#include <cstring>
#include <iostream>
#define N 100001 int n, m, cnt;
int head[N], to[N << ], val[N << ], next[N << ], dis[N];
bool vis[N]; inline int read()
{
int x = , f = ;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;
for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';
return x * f;
} inline void add(int x, int y, int z)
{
to[cnt] = y;
val[cnt] = z;
next[cnt] = head[x];
head[x] = cnt++;
} inline bool spfa(int u)
{
int i, v;
vis[u] = ;
for(i = head[u]; i ^ -; i = next[i])
{
v = to[i];
if(dis[v] > dis[u] + val[i])
{
dis[v] = dis[u] + val[i];
if(vis[v]) return ;
else if(!spfa(v)) return ;
}
}
vis[u] = ;
return ;
} int main()
{
int i, j, opt, x, y, z;
n = read();
m = read();
memset(head, -, sizeof(head));
for(i = ; i <= m; i++)
{
opt = read();
x = read();
y = read();
if(opt == ) add(x, y, ), add(y, x, );
else
{
z = read();
if(opt == ) add(x, y, -z);
if(opt == ) add(y, x, z);
}
}
memset(dis, / , sizeof(dis));
for(i = ; i <= n; i++) add(, i, );
dis[] = ;
spfa() ? puts("Yes") : puts("No");
return ;
}

版权声明:本文内容来源于网络,版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。文本页已经标记具体来源原文地址,请点击原文查看来源网址,站内文章以及资源内容站长不承诺其正确性,如侵犯了您的权益,请联系站长如有侵权请联系站长,将立刻删除

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信图片_20190322181744_03.jpg

微信扫一扫打赏

请作者喝杯咖啡吧~

支付宝扫一扫领取红包,优惠每天领

二维码1

zhifubaohongbao.png

二维码2

zhifubaohongbao2.png