BZOJ_3436_小K的农场

BZOJ_3436_小K的农场_差分约束

题意：

小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:0

spfa求最长路判断有没有正环即可

因为图不一定连通所以要每个连通块都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");

}

巴特西

BZOJ_3436_小K的农场_差分约束

最新文章

热门文章