bzoj3436: 小K的农场（差分约束)

3436: 小K的农场

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1575 Solved: 690
[Submit][Status][Discuss]

Description

背景

小K是个特么喜欢玩MC的孩纸。。。

描述

小K在MC里面建立很多很多的农场，总共n个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得

一些含糊的信息（共m个），以下列三种形式描述：农场a比农场b至少多种植了c个单位的作物，农场a比农场b至多

多种植了c个单位的作物，农场a与农场b种植的作物数一样多。但是，由于小K的记忆有些偏差，所以他想要知道存

不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。

Input

第一行包括两个整数n和m，分别表示农场数目和小K记忆中的信息的数目接下来m行：如果每行的第一个数是1，接

下来有三个整数a,b,c，表示农场a比农场b至少多种植了c个单位的作物如果每行第一个数是2，接下来有三个整数a

，b，c，表示农场a比农场b至多多种植了c个单位的作物如果每行第一个数是3，接下来有两个整数a,b，表示农场a

种植的数量与b一样。1<=n,m,a,b,c<=10000

Output

如果存在某种情况与小K的记忆吻合，输出”Yes”，否则输出”No”

Sample Input

3 3
3 1 2
1 1 3 1
2 2 3 2

Sample Output

Yes
样例解释
三个农场种植的数量可以为（2,2,1）

/*

差分约束

根据限制条件建图，注意要有一个超级源点向所有点连一条边权为0的边

建图看代码。

然后spfa判负环，写bfs会超时的......实测n遍。

*/

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#define inf 0x7fffffff

#define ll long long

#define N 100007

using namespace std;

int n,m,cnt;

int head[N],dis[N];

bool flag,ins[N];

struct edge

{

    int to,next,v;

} e[N];

void add(int u,int v,int w)

{

    e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].v=w;

}

inline ll read()

{

    ll x=,f=;char c=getchar();

    while(c>''||c<''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

void spfa(int x)

{

    ins[x]=;

    for(int i=head[x]; i; i=e[i].next)

        if(e[i].v+dis[x]>dis[e[i].to])

        {

            if(ins[e[i].to])

            {

                flag=;return;

            }

            else

            {

                dis[e[i].to]=e[i].v+dis[x];

                spfa(e[i].to);

            }

        }

    ins[x]=;

}

bool check()

{

    for(int i=; i<=n; i++)dis[i]=ins[i]=;

    flag=;

    for(int i=; i<=n; i++)

    {

        spfa(i);

        if(flag)return ;

    }

    return ;

}

int main()

{

    n=read();m=read();

    for(int i=; i<=m; i++)

    {

        int f=read();

        int a=read(),b=read(),c;

        if(f==)

        {

            c=read();

            if(a==b) {printf("No");return ;}

            add(b,a,c);

        }

        else if(f==)

        {

            c=read();

            if(a==b) {printf("No");return ;}

            add(a,b,-c);

        }

        else add(a,b,),add(b,a,);

    }

    for(int i=n; i>; i--)add(,i,);

    if(check()) {printf("No");return ;}

    printf("Yes");

    return ;

}

巴特西