loj2436 糖果

传送门

分析

我们知道对于一个不等式a<b可以将其转化为a+1<=b的形式，在知道这个之后我们便可以将5个关系进行差分约束了，具体的建边方式见代码。注意由于每个人都必须有糖，我们把每个人的初值都赋为1并全部入队。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

#define pb push_back

#define mp make_pair

queue<int>q;

vector<pair<int,int> >v[];

int d[],vis[],iq[],n;

inline void bad(){

      puts("-1");

      exit();

}

inline void spfa(){

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

          vis[i]=;

          d[i]=;

          q.push(i);

          iq[i]=;

      }

      while(!q.empty()){

          int x=q.front();

          q.pop();iq[x]=;

          for(int i=;i<v[x].size();i++){

            int y=v[x][i].first,z=v[x][i].second;

            if(d[y]<d[x]+z){

                d[y]=d[x]+z;

                vis[y]++;

                if(vis[y]>=n)bad();

                if(!iq[y]){

                  q.push(y);

                  iq[y]=;

                }

            }

          }

      }

}

int main(){

      int m,i,j,k;

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

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

          int x,y;

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

          if(k==){

            v[x].pb(mp(y,));

            v[y].pb(mp(x,));

          }else if(k==){

            if(x==y)bad();

            v[x].pb(mp(y,));

          }else if(k==){

            v[y].pb(mp(x,));

          }else if(k==){

            if(x==y)bad();

            v[y].pb(mp(x,));

          }else {

            v[x].pb(mp(y,));

          }

      }

      spfa();

      long long ans=;

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

      printf("%lld\n",ans);

      return ;

}