BZOJ2330:[SCOI2011]糖果(差分约束)

Description

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

Input

输入的第一行是两个整数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个小朋友分到的糖果；

Output

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

Sample Input

5 7

1 1 2

2 3 2

4 4 1

3 4 5

5 4 5

2 3 5

4 5 1

Sample Output

HINT

【数据范围】

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

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

Solution

差分约束……好像题不是很多的样子
若要求最小值，则将式子化为X-Y>=K,连(Y,X,K)，求最长路
若要求最大值，则将式子化为X-Y<=K,连(Y,X,K)，求最短路
这个题可能会炸longlong
SPFA会被卡所以0点向别的点连边时要倒着连

Code

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<queue>

 #define N (200000+100)

 using namespace std;

 struct node

 {

     int len,next,to;

 } edge[N*];

 int head[N],num_edge;

 int cnt[N],n,m;

 long long dis[N],ans;

 bool used[N];

 queue<int>q;

 void add(int u,int v,int l)

 {

     edge[++num_edge].to=v;

     edge[num_edge].next=head[u];

     edge[num_edge].len=l;

     head[u]=num_edge;

 }

 bool Spfa()

 {

     memset(dis,-0x3f,sizeof(dis));

     q.push();

     dis[]=;

     used[]=true;

     while (!q.empty())

     {

         int x=q.front();

         q.pop();

         for (int i=head[x]; i!=; i=edge[i].next)

             if (dis[x]+edge[i].len>dis[edge[i].to])

             {

                 dis[edge[i].to]=dis[x]+edge[i].len;

                 if (!used[edge[i].to])

                 {

                     q.push(edge[i].to);

                     cnt[edge[i].to]++;

                     if (cnt[edge[i].to]>=n) return false;

                     used[edge[i].to]=true;

                 }

             }

         used[x]=false;

     }

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

         ans+=dis[i];

     return ans;

 }

 int main()

 {

     int opt,x,y;

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

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

     {

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

         if (opt==) add(x,y,), add(y,x,);

         if (opt==)

         {

             if (x==y)//记得加上特判

             {

                 printf("-1");

                 return ;

             }

             add(x,y,);

         }

         if (opt==) add(y,x,);

         if (opt==)

         {

             if (x==y)//记得加上特判

             {

                 printf("-1");

                 return ;

             }

             add(y,x,);

         }

         if (opt==) add(x,y,);

     }

     for (int i=n; i>=; --i) add(,i,);

     if (!Spfa()) printf("-1");

     else printf("%lld",ans);

 }

秒客网