BZOJ_3436_小K的农场_差分约束

开发者子阳技术 2022年11月21日

0 收藏 747 点赞 3,160 浏览 1226 个字

题意：

小K在MC里面建立很多很多的农场，总共n个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共m个），以下列三种形式描述：农场a比农场b至少多种植了c个单位的作物，农场a比农场b至多多种植了c个单位的作物，农场a与农场b种植的作物数一样多。但是，由于小K的记忆有些偏差，所以他想要知道存不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。分析：差分约束对于1操作，b->a:c对于2操作，a->b:-c对于3操作，a->b:0 b->a:0spfa求最长路判断有没有正环即可因为图不一定连通所以要每个连通块都spfa一遍代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stdlib.h>
using namespace std;
#define N 10050
int Q[N],l,r;
int n,m,head[N],to[N<<1],nxt[N<<1],val[N<<1],cnt,vis[N];
int dep[N],dis[N],inq[N];
inline void add(int u,int v,int w)
{
    to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;val[cnt]=w;
}
void spfa(int s)
{
    vis[s]=0;
    int i;
    l=r=0;
    dis[s]=0;
    Q[r++]=s;inq[s]=1;
    while(l^r)
    {
        int x=Q[l++];inq[x]=0;if(l==n+1)l=0;
        vis[x]=1;
        for(i=head[x];i;i=nxt[i])
        {
            if(dis[to[i]]<dis[x]+val[i])
            {
                dep[to[i]]=dep[x]+1;
                if(dep[to[i]]>n)
                {
                    puts("No");exit(0);
                }
                dis[to[i]]=dis[x]+val[i];
                if(!inq[to[i]])
                {
                    Q[r++]=to[i];
                    inq[to[i]]=1;
                    if(r==n+1)r=0;
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    //memset(dis,0x3f,sizeof(dis));
    int i,x,y,z,opt;
    for(i=1;i<=m;i++)
    {
        scanf("%d",&opt);
        if(opt==1)
        {
            scanf("%d%d%d",&x,&y,&z);
            add(y,x,z);
        }
        else if(opt==2)
        {
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,-z);
        }
        else
        {
            scanf("%d%d",&x,&y);
            add(x,y,0);
            add(y,x,0);
        }
    }
    for(i=1;i<=n;i++)if(!vis[i])spfa(i);
    puts("Yes");
}