关于差分约束题目连边方式的疑问

这题大部分人都是按照不等式

X_a - X_b >= C

建的正权边，边权为

0

或

1

，跑最长路，判断正环。我是

X_a - X_b <= C

建了负权边，边权

0

或

-1

，跑最短路，判负环。按照一般差分约束连边方向，应该是

X_b \rightarrow X_a

。但是我只有写成

X_a \rightarrow X_b

才能 AC，否则 WA 三个点（开 longlong 了）：

CPP

        std::swap(a, b); // 去掉这一句 wa 三个点
        if (opt == 1)       {  g[b].push_back(Edge(a,  0));  g[a].push_back(Edge(b, 0)); }  // a = b,      a - b <= 0, b - a <= 0
        else if (opt == 2)  {  g[b].push_back(Edge(a, -1));                              }  // a < b,      a - b <= -1
        else if (opt == 3)  {  g[a].push_back(Edge(b,  0));                              }  // a >= b,     b - a <= 0
        else if (opt == 4)  {  g[a].push_back(Edge(b, -1));                              }  // a > b,      b - a <= -1
        else if (opt == 5)  {  g[b].push_back(Edge(a,  0));                              }  // a <= b,     a - b <= 0

求助大佬 dddlt

关于差分约束题目连边方式的疑问

讨论操作

回复

相关推荐

关于差分约束题目连边方式的疑问