【洛谷】【差分约束】小K的农场

题目链接:https://www.luogu.org/problemnew/show/P1993

思路:线性规划+差分约束+SPFA判负环

情况1可以表示为:$a-b>=c$
情况2可以表示为:$b-a>=-c$
情况3可以表示为:$a-b=0$

我们发现当且仅当$b-a>=-c,c>0$且$a-b>=-c,c>0$时出现了矛盾
于是我们按照不等式构图,若有负环则无解,否则有解
上代码↓

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN=10005;

int n,m,p,np,x,y,z;
int h[MAXN],q[MAXN<<1],ln[MAXN];
bool fl;
bool vis[MAXN];
struct rpg{
    int li,nx,ln;
}a[MAXN<<1];

void add(int ls,int nx,int ln)
{
    a[++np]=(rpg){h[ls],nx,ln};
    h[ls]=np;
}

void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d",&p);
        if(p==1) scanf("%d%d%d",&x,&y,&z),add(x,y,-z);
        else if(p==2) scanf("%d%d%d",&x,&y,&z),add(y,x,z);
        else scanf("%d%d",&x,&y),add(x,y,0);
    }return;
}

void spfa(int x)
{
    vis[x]=1;
    for(int i=h[x];i;i=a[i].li){
        if(ln[a[i].nx]>ln[x]+a[i].ln){
            ln[a[i].nx]=ln[x]+a[i].ln;
            if(vis[a[i].nx]){
                fl=1;return;
            }spfa(a[i].nx);
        }
    }vis[x]=0;
}

void solve()
{
    for(int i=1;i<=n;++i){
        ln[i]=0;
        spfa(i);
        if(fl){
            puts("No");
            return;
        }
    }puts("Yes");
}

int main()
{
    init();
    solve();
    return 0;
}