P1993 小 K 的农场

题目描述：

n个农场，m个条件

• a比b至少多种了c个植物
• a比b至多多种了c个植物
• a和b种的植物数量一样多

问是否存在一种情况满足所有条件

思路：

还是利用前缀和的思维

求满足题意的一种情况，可以用最短路，也就是转换成<=

• 条件1：$sum[b] - sum[a - 1] >= c$,可以转换成 $sum[a-1]<=sum[b]-c$,从b到a-1建立一条权值为-c的边
• 条件2: $sum[b] - sum[a - 1] <=c$可以转换成 $sum[b]<=sum[a - 1]+ c$，可以从a-1到b建立一条权值为c的边
• 条件3: sum[b] = sum[a], 可以转换成 $sum[b] <= sum[a] + 0$ 和 $sum[a] <= sum[b] + 0$，可以从a到b建立一条权值为0的边，再从b到a建立一条权值为0的边

跑最短路看看有没有解就行

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m;
int a, b, c, op;
int tot;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}
bool vis[MAX];
int dis[MAX];
int cnt[MAX];
void SPFA(){
    queue<int>q;
    for(int i = 1; i <= n; ++i){
        vis[i] = 1;
        q.push(i);
    }
    while (!q.empty()) {
        int u = q.front();q.pop();vis[u] = 0;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] > dis[u] + tr[i].val){
                dis[v] = dis[u] + tr[i].val;
                cnt[v] = cnt[u] + 1;
                if(cnt[v] >= n){
                    cout << "No" << endl;
                    return;
                }
                if(!vis[v]){
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    cout << "Yes\n";
}

void work(){
    cin >> n >> m;
    while (m--) {
        cin >> op >> a >> b;
        if(op == 3){
            add(a, b, 0);
            add(b, a, 0);
        }
        else if(op == 1){
            cin >> c;
            add(a, b, -c);
        }
        else{
            cin >> c;
            add(b, a, c);
        }
    }
    SPFA();
}


int main(){
    io;
    work();
    return 0;
}