P1993 小 K 的农场

题目描述

小 K 在 MC 里面建立很多很多的农场，总共 $n$ 个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共 $m$ 个），以下列三种形式描述：

• 农场 $a$ 比农场 $b$ 至少多种植了 $c$ 个单位的作物；
• 农场 $a$ 比农场 $b$ 至多多种植了 $c$ 个单位的作物；
• 农场 $a$ 与农场 $b$ 种植的作物数一样多。

但是，由于小 K 的记忆有些偏差，所以他想要知道存不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。

输入格式

第一行包括两个整数 $n$ 和 $m$，分别表示农场数目和小 K 记忆中的信息数目。

接下来 $m$ 行：

• 如果每行的第一个数是 $1$，接下来有三个整数 $a,b,c$，表示农场 $a$ 比农场 $b$ 至少多种植了 $c$ 个单位的作物；
• 如果每行的第一个数是 $2$，接下来有三个整数 $a,b,c$，表示农场 $a$ 比农场 $b$ 至多多种植了 $c$ 个单位的作物;
• 如果每行的第一个数是 $3$，接下来有两个整数 $a,b$，表示农场 $a$ 种植的的数量和 $b$ 一样多。

提示

对于 $100\mathrm{\%}$ 的数据，保证 $1\le n,m,a,b,c\le 5\times {10}^3$。

思路

参考自iowiki

差分约束, 转化成图论的问题, 判断有没有负环

题解

#include <iostream>
#include <queue>
// #include <list>
#include <list>
#include <vector>

using namespace std;

struct edge
{
    /* data */
    int weight;
    int other;
};

struct node
{
    /* data */
    list<edge> edges;
};

struct graph
{
    /* data */
    node nodes[5010];
    int n;
    graph(int n) : n(n) {}
    void addEdge(int start, int other, int weight)
    {
        // nodes[start].edges.
        nodes[start].edges.push_back({weight, other});
    }

    void test()
    {
        const int INF = 0x3f3f3f3f;
        vector<int> dist(n, INF);
        dist[0] = 0;
        // vector<int> quecount(n, 0);
        queue<int> que;
        vector<int> visited(n, 0);
        que.push(0);
        vector<int> count(n, 0);

        while (!que.empty())
        {
            int now = que.front();
            que.pop();
            visited[now] = 0;
            for (edge &nowegde : nodes[now].edges)
            {
                int other = nowegde.other;
                if (dist[other] > dist[now] + nowegde.weight)
                {

                    dist[other] = dist[now] + nowegde.weight;
                    if (!visited[other])
                    {
                        que.push(other);
                        visited[other] = 1;
                        count[other]++;
                        if (count[other] >= n)
                        {
                            cout << "No";
                            return;
                        }
                    }
                }
            }
        }
        cout << "Yes";
    }
};

int main()
{
    int n, m;
    cin >> n >> m;
    graph gra(n + 1);
    int op, a, b, d;

    for (int i = 0; i < m; i++)
    {
        cin >> op;
        if (op == 1)
        {
            // a - b >= c
            //  b - a <= -c
            cin >> a >> b >> d;
            gra.addEdge(a, b, -d);
        }
        else if (op == 2)
        {
            // a - b <= c
            cin >> a >> b >> d;
            gra.addEdge(b, a, d);
        }
        else
        {
            cin >> a >> b;
            gra.addEdge(b, a, 0);
            gra.addEdge(a, b, 0);
        }
    }
    // 添加一个额外点,到所有点边权为0,防止不图不连通
    for (int i = 0; i < n; i++)
    {
        gra.addEdge(0, i + 1, 0);
    }

    gra.test();
    return 0;
}