Luogu P1993 小 K 的农场

　　其实很早以前就打好了，但一直忘记写了。

　　也就是差分约束的模板题。

　　关于差分约束，也就是用来求关于一些不等式互相约束算出最优解。

　　推荐一个讲的很好的博客：http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html

　　可以通过一个三角形不等式来搞一下：

　　B - A <= c (1)

　　C - B <= a (2)

　　C - A <= b (3)

　　如果我们想要知道C - A的最大值，通过(1) + (2)，可以得到 C - A <= a + c，所以这个问题其实就是求min{b, a+c}。

　　所以这题只需要转换一下不等式，用SPFA来判负环（用DFS比较快）

　　CODE

#include<cstdio>

#include<cstring>

using namespace std;

const int N=;

struct data

{

    int to,next,v;

}e[N];

int head[N],dis[N],n,m,opt,i,j,x,y,z,k,h,t;

bool flag=,vis[N];

inline void read(int &x)

{

    x=; char ch=getchar();

    while (ch<''||ch>'') ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

}

inline void add(int x,int y,int z)

{

    e[++k].to=y; e[k].v=z; e[k].next=head[x]; head[x]=k;

}

inline void SPFA(int k)

{

    vis[k]=;

    for (int i=head[k];i!=-;i=e[i].next)

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

    {

        if (vis[e[i].to]) { flag=; return; }  else dis[e[i].to]=dis[k]+e[i].v,SPFA(e[i].to);

    }

    vis[k]=;

}

int main()

{

    read(n); read(m);

    memset(e,-,sizeof(e));

    memset(head,-,sizeof(head));

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

    {

        read(opt);

        if (opt==) read(x),read(y),read(z),add(x,y,-z);

        if (opt==) read(x),read(y),read(z),add(y,x,z);

        if (opt==) read(x),read(y),add(x,y,),add(y,x,);

    }

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

    {

        if (flag) break;

        memset(dis,,sizeof(dis));

        SPFA(i);

    }

    if (flag) puts("No"); else puts("Yes");

    return ;

}

巴特西

Luogu P1993 小 K 的农场

最新文章

热门文章