loj2436 糖果-白红宇

loj2436 糖果

阅读量：7112 次

发布时间：2019-06-28

本文共 1176 字，大约阅读时间需要 3 分钟。

分析

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

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;#define pb push_back#define mp make_pairqueue
                   
                    q;vector
                    
                     
                       >v[100010];int d[100010],vis[100010],iq[100010],n;inline void bad(){ puts("-1"); exit(0);}inline void spfa(){ for(int i=1;i<=n;i++){ vis[i]=1; d[i]=1; q.push(i); iq[i]=1; } while(!q.empty()){ int x=q.front(); q.pop();iq[x]=0; for(int i=0;i
                      
                       =n)bad(); if(!iq[y]){ q.push(y); iq[y]=1; } } } }}int main(){ int m,i,j,k; scanf("%d%d",&n,&m); for(i=1;i<=m;i++){ int x,y; scanf("%d%d%d",&k,&x,&y); if(k==1){ v[x].pb(mp(y,0)); v[y].pb(mp(x,0)); }else if(k==2){ if(x==y)bad(); v[x].pb(mp(y,1)); }else if(k==3){ v[y].pb(mp(x,0)); }else if(k==4){ if(x==y)bad(); v[y].pb(mp(x,1)); }else { v[x].pb(mp(y,0)); } } spfa(); long long ans=0; for(i=1;i<=n;i++)ans+=(long long)d[i]; printf("%lld\n",ans); return 0;}

转载于:https://www.cnblogs.com/yzxverygood/p/9516197.html

你可能感兴趣的文章

eclipse中报错：java.lang.OutOfMemoryError: Java heap space