【题目描述】：

幼儿园里有N个小朋友,1xhgww老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候lkhgww需要满足小朋友们的K个要求。幼儿园的糖果总数是有限的，1xhgww想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果,并且满足小朋友们所有的要求。

PS：出题人/搬题人太毒，建图顺序不对会导致#5会TLE/WA。。。

【输入描述】：

输人的第一行是两个整数N,K。

接下来K行，表示这些点需要满足的关系，每行3个数字,X,A,B。

如X=1,表示第A个小朋友分到的糖果必须和第B个小朋友分到的糖果一样多。

如X=2,表示第A个小朋友分到的糖果必须少于第B个小朋友分到的糖果。

如X=3,表示第A个小朋友分到的糖果必须不少于第B个小朋友分到的糖果。

如X=4,表示第A个小朋友分到的糖果必须多于第B个小朋友分到的糖果。

如X=5,表示第A个小朋友分到的糖果必须不多于第B个小朋友分到的糖果。

【输出描述】：

输出一行，表示lxhgww老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出-1。

【样例输入】： 5 7 1 1 2 2 3 2 4 4 1 3 4 5 5 4 5 2 3 5 4 5 1

【样例输出】： 11

【时间限制、数据范围及描述】：

时间：1s 空间：128M

对于30%的数据，保证N<=100。

对于100%的数据，保证N<=100,000。

对于所有的数据，保证K<=100,000；1<=X<=5；1<=A,B<=N。

代码

#include
     
      #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            using namespace std; queue 
           
             q; int tot,cnt,front[500005],n,k; long long ans; int dis[500005],flag[500005],ring[500005],nxt[500005],head[500005],endd[500005],w[500005]; inline void Add(int u,int v,int k){ nxt[++cnt]=head[u]; head[u]=cnt; endd[cnt]=v; w[cnt]=k; return ; } inline int read(){ int ans=0,ok=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')ok=-1; ch=getchar(); } for (;ch>='0'&&ch<='9';ch=getchar()) ans=ans*10+ch-'0'; return ans*ok; } inline bool SPFA(){ while(!q.empty()){ int u=q.front(); q.pop(); flag[u]=0; if(ring[u]==n-1){ printf("-1\n"); return 0; } ring[u]++; for(int i=head[u];i;i=nxt[i]){ if(dis[endd[i]]
            
             =n-1)return false; if(!flag[endd[i]]){ flag[endd[i]]=1; q.push(endd[i]); } } } } return true; } int main() { n=read(); k=read(); for(int i=1; i<=k; i++) { int x,a,b; x=read(); a=read(); b=read(); if(x==1){ Add(a,b,0); Add(b,a,0); } else if(x==2){Add(a,b,1);} else if(x==3){Add(b,a,0);} else if(x==4){Add(b,a,1);} else if(x==5){Add(a,b,0);} if(x%2==0&&a==b){ printf("-1\n"); return 0; } } for(int i=n;i>=1;i--){ Add(0,i,1); } flag[0]=1; q.push(0); if(!SPFA()){ printf("-1\n"); return 0; } for(int i=1;i<=n;i++){ ans+=dis[i]; } printf("%lld\n",ans); return 0; }
            
           
          
         
        
       
      
     

分情况讨论。