2330: [SCOI2011]糖果
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 2306 Solved: 647
[Submit][Status]
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
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1
Sample Output
11
差分约束
//#define _TEST _TEST #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <cmath> #include <algorithm> #include <queue> using namespace std; /************************************************ Code By willinglive ************************************************/ ///////////////////////////////////////////////// #define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++) #define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--) #define MS(arr,x) memset(arr,x,sizeof(arr)) #define LL long long #define INE(i,u,e) for(int i=head[u];~i;i=e[i].next) ///////////////////////////////////////////////// int n,k; LL a[100010]; queue<int>q; bool inq[100010]; int relax[100010]; struct edge{int v,w,next;}e[200000]; int head[100010],kk; ///////////////////////////////////////////////// void adde(int u,int v,int w){e[kk].v=v;e[kk].w=w;e[kk].next=head[u];head[u]=kk++;} bool spfa() { while(!q.empty()) { int u=q.front(); q.pop(); inq[u]=0; INE(i,u,e) { int v=e[i].v; if(a[v]<a[u]+e[i].w) { a[v]=a[u]+e[i].w; if(++relax[v]>=n) return 0; if(!inq[v]) q.push(v),inq[v]=1; } } } return 1; } ///////////////////////////////////////////////// bool input() { MS(head,-1); scanf("%d%d",&n,&k); int x,a,b; rep(i,1,k) { scanf("%d%d%d",&x,&a,&b); switch(x) { case 1://a=b adde(a,b,0); adde(b,a,0); break; case 2://a<b if(a==b) return 0; adde(a,b,1); break; case 3://a>=b adde(b,a,0); break; case 4://a>b if(a==b) return 0; adde(b,a,1); break; case 5://a<=b adde(a,b,0); break; } } return 1; } void solve() { ///////////////////init/////////////////// LL ans=0; rep(i,1,n) a[i]=1,q.push(i),inq[i]=1; ////////////////calculate//////////////// if(!spfa()) { puts("-1"); return; } rep(i,1,n) ans+=a[i]; /////////////////output///////////////// printf("%lld\n",ans); } ///////////////////////////////////////////////// int main() { #ifndef _TEST freopen("std.in","r",stdin); freopen("std.out","w",stdout); #endif if(!input()) puts("-1"); else solve(); #ifdef _TEST for(;;); #endif return 0; }