Description

小 K 是个特么喜欢玩 MC 的孩纸......

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

  1. 农场 \(a\) 比农场 \(b\) 至少多种植了 \(c\) 个单位的作物;
  2. 农场 \(a\) 比农场 \(b\) 至多多种植了 \(c\) 个单位的作物;
  3. 农场 \(a\) 与农场 \(b\) 种植的作物数一样多.

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

Input

第一行包括两个整数 \(n\) 和 \(m\), 分别表示农场数目和小 K 记忆中的信息的数目;

接下来 \(m\) 行: 如果每行的第一个数是 \(1\), 接下来有三个整数 \(a, b, c\), 表示农场 \(a\) 比农场 \(b\) 至少多种植了 \(c\) 个单位的作物; 如果每行第一个数是 \(2\), 接下来有三个整数 \(a, b, c\), 表示农场 \(a\) 比农场 \(b\) 至多多种植了 \(c\) 个单位的作物; 如果每行第一个数是 \(3\), 接下来有两个整数 \(a, b\), 表示农场 \(a\) 种植的数量与 \(b\) 一样多.

Output

如果存在某种情况与小 K 的记忆吻合, 输出 Yes, 否则输出 No.

Sample Input

3 3
3 1 2
1 1 3 1
2 2 3 2

Sample Output

Yes

Data Range

对于 100% 的数据,\(1 \leq n, m, a, b, c \leq 10000\)

Explanation

把 vis 更新写到外面我也是醉了 QwQ

就是一个差分约束系统模板题, 话说好久没有写判负权回路的模板题我实在是容易写挂......

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;
// typedef long long lli;
typedef int lli;
const int maxn = 20100, maxm = 100010;
// const lli infinit = 0x007f7f7f7f7f7f7fll;
const lli infinit = 1000000000;

class SPFA
{
public:
    struct edge {
        int u, v;
        lli len;
        edge *next;
    };
    int n, s, ecnt;
    edge *edges[maxn], epool[maxm];
    void add_edge(int u, int v, lli len)
    {
        edge *p = &epool[++ecnt];
        p->u = u; p->v = v; p->len = len;
        p->next = edges[u]; edges[u] = p;
        return ;
    }
    lli dist[maxn];
    bool inque[maxn];
    int vis[maxn];
    bool eval(void)
    {
        queue<int> que;
        dist[s] = 0;
        inque[s] = 1;
        que.push(s);
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            inque[p] = false;
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (dist[p] + ep->len < dist[ep->v]) {
                    dist[ep->v] = dist[p] + ep->len;
                    if (inque[ep->v] <= 0) {
                        que.push(ep->v);
                        inque[ep->v] = true;
                        vis[ep->v] = vis[p] + 1;
                        if (vis[ep->v] > n)
                            return false;
                    }
                }
            continue;
        }
        return true;
    }
    void init(void)
    {
        for (int i = 1; i <= n; i++) {
            dist[i] = infinit;
            inque[i] = false;
            vis[i] = 0;
        }
        return ;
    }
} graph;

int n, m;

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    graph.n = n;
    graph.init();
    for (int i = 1, t, a, b, c; i <= m; i++) {
        scanf("%d%d%d", &t, &a, &b);
        if (t == 1) {
            scanf("%d", &c);
            graph.add_edge(a, b, -c);
        } else if (t == 2) {
            scanf("%d", &c);
            graph.add_edge(b, a, c);
        } else {
            graph.add_edge(a, b, 0);
            graph.add_edge(b, a, 0);
        }
    }
    // Evaluating result
    bool res = true;
    for (int i = 1; i <= n; i++) {
        graph.s = i;
        if (graph.dist[i] < infinit)
            continue;
        bool tmp = graph.eval();
        if (!tmp) {
            res = false;
            break;
        }
    }
    printf("%s\n", res ? "Yes" : "No");
    return 0;
}