[Leaf] [P1993] 小K的农场

p1993-小-k-的农场---洛谷">P1993 小 K 的农场 - 洛谷

1. 题面梗概

中译中：给一堆农场变量 $x_1, x_2, \dots, x_n$。给出三种“大小关系”的约束（大于、等于、小于），问这些约束在一起会不会矛盾。

2. 逻辑推导

这是 差分约束 的例题，关键在于将 代数不等式 转化成 图论中三角不等式。

2.1 映射

在单源最短路算法中，松弛操作的核心是不等式：

$$dist[v] \le dist[u] + w(u, v)$$

这在代数上可以变形为：

$$dist[v] - dist[u] \le w(u, v)$$

这意味着，如果我们有一个 $x_v - x_u \le w$ 的约束，就可以连一条从 $u$ 到 $v$ 权值为 $w$ 的有向边。

2.2 翻译

我们要把题目中的不等式翻译成标准的 $x_v \le x_u + w$ 形式：

1. $a$ 比 $b$ 至少多 $c$：

   • 代数：$x_a - x_b \ge c \implies x_b \le x_a - c$

   • 转化：从 $a$ 连向 $b$ 一条权值为 $-c$ 的边。

2. $a$ 比 $b$ 至多多 $c$：

   • 代数：$x_a - x_b \le c \implies x_a \leq x_b + c$

   • 转化：从 $b$ 连向 $a$ 一条权值为 $c$ 的边。

3. $a$ 与 $b$ 一样多：

   • 代数：$x_a = x_b$ $\iff$ $x_a \le x_b + 0$ 且 $x_b \le x_a + 0$

   • 转化：$a, b$ 之间连双向权值为 $0$ 的边。

2.3 结论

如果图中出现负环，意味着在一圈约束条件中，出现了类似 $x_i < x_i$ 的荒谬结论。这种情况就意味着不等式组出现了矛盾。

3. 代码实现

▶

AcCode

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 5e3 + 5;
const ll inf = 1e18;

struct Edge { int v, w; };
vector< Edge > adj[maxn];
ll dist[maxn];
int cnt[maxn];
bool inq[maxn];
int a, b, c, n, m;

bool spfa( )
{
    queue< int > q;
    for( int i = 1; i <= n; ++ i )
    {
        dist[i] = 0;
        q.push( i ), inq[i] = true;
    }

    while( !q.empty( ) )
    {
        int u = q.front( );
        q.pop( ), inq[u] = false;

        for( auto& [v, w] : adj[u] )
        {
            if( dist[u] + w < dist[v] )
            {
                dist[v] = dist[u] + w;
                cnt[v] = cnt[u] + 1;
                if( cnt[v] >= n ) return true;
                if( !inq[v] ) q.push( v ), inq[v] = true;
            }
        }
    }
    return false;
}

int main( )
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    for( int i = 1; i <= m; ++ i ) 
    {
        int opt;
        cin >> opt >> a >> b;
        if( opt == 1 )
        {
            cin >> c;
            adj[a].push_back({ b, -c });
        }
        else if( opt == 2 )
        {
            cin >> c;
            adj[b].push_back({ a, c });
        }
        else
        {
            adj[a].push_back({ b, 0 });
            adj[b].push_back({ a, 0 });
        }
    }

    if( spfa( ) ) cout << "No" << '\n';
    else cout << "Yes" << '\n';

    return 0;
}

4. 复盘

• 复杂度分析：SPFA $O(NM)$。

• Trick：注意连通性，如果图不连通，单一源点可能漏掉某些负环。所以采用超级源点将所有点入队，确保判断完备。

• 碎碎念：注意不等式的方向。如果 a - b >= c 连成了 b -> a 权值为 c 的边，那就寄了。

$X_{v} \leq X_{u} + w$，连一条 $u \to v$ 的权值为 $w$ 的边。

• 关联笔记：最短路体系