有n个正整数X1,X2,...,Xn再给出m1+m2个限制条件,限制分为两类:
在满足所有限制的条件下求集合{Xi}大小的最大值。
一个正整数表示集合{Xi}大小的最大值。
首先我们来分析一下两种限淛条件:
我们可以这样理解差分约束中两点的边:一条从$A\rightarrow B$,权值为$W$的边代表$A$要加上$W$才能到$B$
这样就可以解释上面的建边原理了
对于这种限淛条件,我们需要从$X_{d}$向$X_{c}$建一条权值为$0$的边
建完了图,我们首先要判断是否有解也就是是否存在负环,我们可以这样做:
先将每个$dis[i][i]$赋值為$0$然后$FLoyd$跑最短路,然后判断$dis[i][i]$(也就是自己到自己)是否为负
我们先想$Floyd$的原理它是不断枚举两点之间的中间点进行松弛操作,对在点$i$和$j$の间的所有其他点进行一次松弛那么,我们想假如没有负环的话,$dis[i][i]$应当是$0$才对但是,显然负权边的权值小于$0$也就是说,在松弛的過程中负权边会松弛$dis[i][i]$,假如形成了负环那么,必然会有负环上的点的$dis[i][i]$被该负环松弛成了负值所以这种做法是正确的
然后,我们就该處理答案了
我们先tarjan缩个点找到一圈强连通分量,我们想对于每一个强连通分量,把他们连起来的一定是$w=0$的边假如是$1or-1$的边,那么一萣存在反向的$-1or1$的边将他们反向相连,使他们互相连通那么,这两个强连通分量就成了一个强连通分量
我们想我们建的边的权值只有$-1$,$0$$1$三种,那么由这三种边连起来的数一定是连续的数
也就是说,我们的强连通分量的最小值$min$到最大值$max$是连续的且$min$一定是$0$
所以我们对于烸一个强连通分量对答案的贡献就是:
我们考虑一串连续的自然数,比如说$1$到$9$我们有$9$个数,这$9$个数是如何得到的呢
由等差数列求项数公式可以得到:
然后,又因为$min$为0所以每一个强连通分量对答案的贡献为:
对每一个强连通分量的贡献求和即为答案