BZOJ3436——小K的农场

1、题意：大概是给一些制约限制，问是否存在合法解

2、分析：我们来观察这三个限制

农场a比农场b至少多种植了c个单位的作物可以变成b 比 a至多多种了-c

农场a比农场b至多多种植了c个单位的作物可以变成a 比
b至多多种了c

农场a与农场b种植的作物数一样多
就是a = b

那么利用差分约束我们可以把这个东西转为一个图，那么如果这个图中有正环那么这个图就是不合法的，如何判断有没有正环呢？

我们可以利用spfa求最短路时判负环，我们把它改成求最长路时，判正环，然后就AC了

#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define M 1000010
#define inf 1047483647

inline int read(){
    char ch = getchar(); int x = 0, f = 1;
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while('0' <= ch && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

struct Edge{
    int u, v, w, next;
} G[M];
int head[M], tot;

int inq[M], d[M];
int n, m;

inline void add(int u, int v, int w){
    G[++ tot] = (Edge){u, v, w, head[u]};
    head[u] = tot;
}

inline bool spfa(){
    for(int i = 1; i <= n; i ++) d[i] = -inf;
    queue<int> Q;
    Q.push(0);
    while(!Q.empty()){
        int x = Q.front(); Q.pop(); inq[x] = 0;
        for(int i = head[x]; i != -1; i = G[i].next){
            if(d[G[i].v] < d[x] + G[i].w){
                if(inq[G[i].v]){
                    return false;
                }
                d[G[i].v] = d[x] + G[i].w;
                Q.push(G[i].v);
                inq[G[i].v] = 1;
            }
        }
    }
    return true;
}

int main(){
    n = read(), m = read();
    memset(head, -1, sizeof(head));
    for(int i = 1; i <= m; i ++){
        int op = read();
        if(op == 2){
            int a = read(), b = read(), c = read();
            add(a, b, c);
        }
        else if(op == 1){
            int a = read(), b = read(), c = read();
            add(b, a, -c);
        }
        else{
            int a = read(), b = read();
            add(a, b, 0);
            add(b, a, 0);
        }
    }
    for(int i = 1; i <= n; i ++) add(0, i, 0);
    if(spfa()) puts("Yes");
    else puts("No");
    return 0;
}

巴特西

BZOJ3436——小K的农场

最新文章

热门文章