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

3436: 小K的农场

题目：传送门

题解：
　　 查分基础：

　　 t==1  a>=b+c

　　 t==2  b>=a-c

　　t==3  a>=b+0 b>=a+0

　　 跑最长路一A

代码：

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 int n,m;

 struct node

 {

     int x,y,d,next;

 }a[];int len,last[];

 void ins(int x,int y,int d)

 {

     len++;a[len].x=x;a[len].y=y;a[len].d=d;

     a[len].next=last[x];last[x]=len;

 }

 bool v[];int d[],ru[],list[];

 int main()

 {

     scanf("%d%d",&n,&m);

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

     {

         int t,x,y,d;

         scanf("%d%d%d",&t,&x,&y);

         if(t==)scanf("%d",&d),ins(y,x,d);

         if(t==)scanf("%d",&d),ins(x,y,-d);

         if(t==)ins(x,y,),ins(y,x,);

     }

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

     int head=;for(int i=n;i>=;i--)list[++head]=i;

     memset(v,,sizeof(v));memset(ru,,sizeof(ru));

     bool bk=true;

     while(head!=)

     {

         int x=list[head--];v[x]=true;

         for(int k=last[x];k;k=a[k].next)

         {

             int y=a[k].y;

             if(d[y]<d[x]+a[k].d)

             {

                 d[y]=d[x]+a[k].d;

                 ru[y]++;if(ru[y]==n+){bk=false;break;}

                 if(v[y]==true)v[y]=false,list[++head]=y;

             }

         }

         if(bk==false)break;

     }

     if(bk==true)printf("Yes\n");

     else printf("No\n");

     return ;

 }