若有重边该怎么取？当然这个题目不会，可是如果改3小时的，如下面的案例：
1
3
1 0 0
1
1
从小到大枚举答案当ans=1时
G[2][1]有两个取值0和-1。这时该怎么取呢？或者这时差分约束已经不适应了？
我构的图源点s=3,目标点t=2
构出的图矩阵表示为
-inf   0    0   -inf
0    -inf   0   -inf
-inf  0/-1 -inf -inf
0      0    0     0

最后一行零表示源点到每一个的距离为0，-inf为不可达，自身与自身的不可达是为了spfa时不加判断语句v!=u。

 还有我对从源点s至目标t的边的理解是dis[t]=ans>0在图中可能会构成正圈，也就是无解的状态，但是不加这条边的话，本来有正圈的（无解）会当成了无正圈(有解）输出！

• Re:求大牛解释！！！各种费解！ (50) ysjjovo 2011-08-13 21:01:31