『题解』洛谷P1993 小K的农场

更好的阅读体验

Portal

Portal1: Luogu

Description

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

农场(a)比农场(b)至少多种植了(c)个单位的作物，
农场(a)比农场(b)至多多种植了(c)个单位的作物，
农场(a)与农场(b)种植的作物数一样多。

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

Input

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

接下来(m)行：

如果每行的第一个数是(1)，接下来有(3)个整数(a, b, c)，表示农场(a)比农场(b)至少多种植了(c)个单位的作物。

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

Output

如果存在某种情况与小(K)的记忆吻合，输出Yes，否则输出No。

Sample Input

Sample Output

Yes

Hint

对于(100\%)的数据保证：(1 le n, m, a, b, c le 10000)。

Solution

我们用(mathrm{s[i]})表示(i)农场的作物数量，那么题目中的条件我们可以表示为：

(s[a] ge s[b] + c)
(s[b] ge s[a] - c)
(s[b] = s[a])

因为我们如果想让这道题用差分约束做，要把所有的约束条件都改为(le)或者(ge)的形式，但是此题的所有农场的做作物数都不能为负数，所以必须要用最长路解决。因此，我们可以改为：

(s[a] ge s[b] + c)
(s[b] ge s[a] - c)
(s[a] ge s[b] + 0)
(s[b] ge s[a] + 0)
(s[i] ge 0)

然后我们开始建边：

对于题目给出的(a, b, c)

(b o a)建一条权值为(c)的边；
(a o b)建一条权值为(-c)的边；
(a o b)建一条权值为(0)的边；
(b o a)键一条权值为(0)的边；

最后在(0 o i, i in [1, n])建权值为(0)的边。

建完之后用(mathrm{SPFA})跑一遍最长路，顺便判断环就可以了。

Code

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>

using namespace std;

const int INF = 0x3f3f3f3f, MAXN = 20005;
struct EDGE {
    int to, nxt, val;
} edge[MAXN];
int n, m, u, v, opt, val, cnt, tot[MAXN], vis[MAXN], dis[MAXN], head[MAXN];
inline void addedge(int u, int v, int val) {//邻接表存图
    edge[++cnt].to = v; edge[cnt].val = val; edge[cnt].nxt = head[u]; head[u] = cnt;
}
inline bool SPFA() {//SPFA最长路
    priority_queue<int> Q;
    memset(dis, -INF, sizeof(dis));
    vis[0] = 1;
    dis[0] = 0;
    tot[0] = 1;
    Q.push(0);
    while (!Q.empty()) {
        int u = Q.top();
        Q.pop();
        vis[u] = 0;
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].to;
            if (dis[v] < dis[u] + edge[i].val) {
                dis[v] = dis[u] + edge[i].val;
                if (!vis[v]) {
                    tot[v] = tot[u] + 1;
                    Q.push(v);
                    vis[v] = 1;
                    if (tot[v] > n) return 0;
                }
            }
        }
    }
    return 1;
}
int main() {
    scanf("%d%d", &n, &m);
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= m; i++) {
        scanf("%d", &opt);
        if (opt == 1) {
            scanf("%d%d%d", &u, &v, &val);
            addedge(u, v, val);
        } else
        if (opt == 2) {
            scanf("%d%d%d", &u, &v, &val);
            addedge(v, u, -val);
        } else {
            scanf("%d%d", &u, &v);
            addedge(u, v, 0);
            addedge(v, u, 0);
        }
    }
    for (int i = 1; i <= n; i++)
        addedge(0, i, 0);//按题目的描述建边
    if (SPFA()) printf("Yes
"); else printf("No
");
    return 0;
}