题意

给定多组限制,限制分成2类,第一类是ax+1=ay 第二类是ax≤ay,求这些数最多有多少种不同的取值

在使得所给的等式成立的情况下,问最多能有多少不同的数字值。


差分约束题目

问最多有多少种取值

那么求最短路判负环

第一类限制可以 换为

\(y-x<=1\)

连边

\(x – > y, w=1\)

\(x-y<=-1\)

连边

\(y – > x ,   w=-1\)

第二类限制直接

\(y->x, w=0\)

对于每个强连通分块之间是没有限制的

于是就可以在每个强连通分块中判负环

最后累加一下答案就行了

 


说点什么

avatar
  Subscribe  
提醒