POJ 1364 King 差分约束

题意:国王的傻儿子会算一段序列的连续子序列的和,并且能告诉别人一段和大于K或者小于K,有些人想谋权篡位所以提了很多个DECISIONS,说一段和大于或者小于K,国王的傻儿子想知道是否有合法序列满足所有DECISIONS

解法其实很直接…就是从0开始到N建边约束就好,但是注意这题0不能当超级源点…因为它一直在变(因为这WA了好几次)
code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#define MAXN 5055
#define INF 19999999
using namespace std;
int N, M;
int u[MAXN],v[MAXN],w[MAXN],nex[MAXN],first[MAXN];
int tot;
int vis[MAXN],cnt[MAXN],d[MAXN];
void add(int x,int y,int z)
{
 u[++tot]=x;
 v[tot]=y;
 w[tot]=z;
 nex[tot]=first[x];
 first[x]=tot;
}
bool spfa()
{
 queue<int> q;
 q.push(N+2);
 memset(vis,0,sizeof(vis));
 memset(cnt,0,sizeof(cnt));
 for(int i=0;i<=N;i++)
 {
  d[i]=-INF;
 }
 d[N+2]=0;
 while(!q.empty())
 {
  int x=q.front();
  q.pop();
  vis[x]=0;
  for(int i=first[x];i;i=nex[i])
  {
   if(d[v[i]]<d[x]+w[i])
   {
    d[v[i]]=d[x]+w[i];
    if(!vis[v[i]])
    {
     vis[v[i]]=1;
     cnt[v[i]]++;
     if(cnt[v[i]]>N+1)
     {
      return false;
     }
     q.push(v[i]);
    }
   }
  }
 }
 return true; 
}
int main()
{
 int i, j, k;
 while(scanf("%d",&N)!=EOF&&N)
 {
 cin>>M;
 tot=0;
 memset(u,0,sizeof(u));
 memset(v,0,sizeof(v));
 memset(w,0,sizeof(w));
 memset(nex,0,sizeof(nex));
 memset(first,0,sizeof(first));
 for(i=1;i<=M;i++)
 {
  int x,y,num;
  string s;
  cin>>x>>y>>s>>num;
  if(s=="gt")
  {
   add(x-1,y+x,num+1);
  }
  if(s=="lt")
  {
   add(y+x,x-1,-num+1);
  } 
 }
 for(i=0;i<=N;i++)
 {
  add(N+2,i,0);
 }
 if(spfa())
 {
  cout<<"lamentable kingdom\n";
 }
 else
 {
  cout<<"successful conspiracy\n";
 }
 }
}