首先这是个查分约束系统。。。（那是啥来着←_←）

然后判断可行解的话，直接spfa判负圈。

bfs版spfa要记录每个点的进队次数，如果大于点数就代表有负圈。。。但是好慢Σ( ° △ °|||)︴

于是改用dfs版的spfa（还以为会很慢。。。，其实速度极快Orz）

 

1 /************************************************************** 2     Problem: 3436 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:36 ms 7     Memory:1236 kb 8 ****************************************************************/ 9  10 #include 
      
       11  12 using namespace std;13 const int N = 10005;14 const int M = N;15 const int Maxlen = 20 * M;16  17 struct edges {18     int next, to, v;19     edges() {}20     edges(int _n, int _t, int _v) : next(_n), to(_t), v(_v) {}21 } e[M];22  23 int n, m;24 int first[N], tot;25 int d[N];26 int v[N], flag;27 char buf[Maxlen], *c = buf;28 int Len;29  30 inline int read() {31     int x = 0;32     while (*c < '0' || '9' < *c) ++c;33     while ('0' <= *c && *c <= '9')34         x = x * 10 + *c - '0', ++c;35     return x;36 }37  38 inline void add_edge(int x, int y, int z) {39     e[++tot] = edges(first[x], y, z);40     first[x] = tot;41 }42  43 void spfa(int p) {44     if (v[p]) {45         flag = 1;46         return;47     }48     int x, y;49     v[p] = 1;50     for (x = first[p]; x; x = e[x].next)51         if (d[p] + e[x].v < d[y = e[x].to]) {52             d[y] = d[p] + e[x].v;53             spfa(y);54             if (flag) return;55         }56     v[p] = 0;57 }58  59 int main() {60     Len = fread(c, 1, Maxlen, stdin);61     buf[Len] = '\0';62     int i, oper, x, y, z;63     n = read(), m = read();64     for (i = 1; i <= m; ++i) {65         oper = read(), x = read(), y = read();66         if (oper == 3) add_edge(x, y, 0);67         else {68             z = read();69             if (oper == 1) add_edge(x, y, -z);70             else add_edge(y, x, z);71         }72     }73     for (i = 1; i <= n; ++i) {74         spfa(i);75         if (flag) break;76     }77     puts(flag ? "No" : "Yes");78     return 0;79 }