P1993 小 K 的农场

· · 题解

思路

先读题，在读到“农场 a 比农场 b 至少多种植了 c 个单位的作物”时我们便可以知道这是一道差分约束了。分析如下：

a-b \leq c$ -->> $b \leq a-c a-b \leq c$ -->> $a \leq b+c a=b

知道了这些之后就可以愉快地建图啦！最后运行还没被迫害的SPFA，如果有负权回路则输出No，否则输出Yes即可！不过记住要用链表，不然会爆掉！

不会SPFA者可以去看下这篇文章，个人认为写得很好！

代码

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
int n,m,w,k=1;
int dis[100000],Last[100000],cnt[100000];
struct node
{
    int l,r,val,Next;
};
node p[100000]; 
queue<int> q;
bool mark[100000];
void add(int u,int v,int w)
{
    p[k].l=u;
    p[k].r=v;
    p[k].val=w;
    p[k].Next=Last[p[k].l];
    Last[p[k].l]=k;
    k++;
}
bool SPFA(int s)
{
    int x;
    for(int i=1;i<=n;i++)dis[i]=inf;
    dis[s]=0;
    q.push(s);
    mark[s]=true;
    cnt[s]++;
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        mark[x]=false;
        for(int i=Last[x];i!=0;i=p[i].Next)
        {
            if(dis[p[i].r]>dis[x]+p[i].val)
            {
                dis[p[i].r]=dis[x]+p[i].val;
                cnt[p[i].r]++;
                if(cnt[p[i].r]==n)return true;
                if(!mark[p[i].r]) 
                {
                    q.push(p[i].r);
                    mark[p[i].r]=true;
                }
            }
        }
    }
    return false;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int op,a,b,c;
        scanf("%d",&op);
        if (op==1)
        {
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,-c);
        }
        else if(op==2)
        {
            scanf("%d%d%d",&a,&b,&c);
            add(b,a,c);
        }
        else if(op==3)
        {
            scanf("%d%d",&a,&b);
            add(a,b,0);
            add(b,a,0);
        }
    }
    for(int i=1;i<=n;i++)add(n+1,i,0);
    if(SPFA(n+1))printf("No");
    else printf("Yes");
}