/*【bzoj2330】[SCOI2011]糖果

2014年3月5日1,2761

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。

?*/

//差分約束題目 注意數據范圍。建立超級原點。

#include<cstdio> #include<iostream> using namespace std; int n,m,cnt,head[100006],next[400006],u[400006],v[400006],h,t,a[100006]; int ci[100006],f[100006]; long long d[100006]; void jia(int a1,int a2,int a3) {cnt++;next[cnt]=head[a1];head[a1]=cnt;u[cnt]=a2;v[cnt]=a3; } int main() {scanf("%d%d",&n,&m);for(int i=0;i<m;i++){int a1,a2,a3;scanf("%d%d%d",&a1,&a2,&a3);if(a1==1){jia(a2,a3,0);jia(a3,a2,0);}if(a1==2){if(a2==a3){printf("-1");return 0;}jia(a2,a3,1);}if(a1==3)jia(a3,a2,0);if(a1==4){if(a2==a3){printf("-1");return 0;}jia(a3,a2,1);}if(a1==5)jia(a2,a3,0);}for(int i=n;i;i--)jia(0,i,1);a[1]=0;ci[0]++;t=1;f[0]=1;for(;h!=t;){h++;if(h>100004)h=1;f[a[h]]=0;for(int i=head[a[h]];i;i=next[i])if(d[u[i]]<d[a[h]]+v[i]){d[u[i]]=d[a[h]]+v[i];ci[u[i]]++;if(ci[u[i]]==n+1){printf("-1\n");return 0;}if(!f[u[i]]){t++;if(t>100004)t=1;a[t]=u[i];f[u[i]]=1;}}}long long ans=0;for(int i=1;i<=n;i++)ans+=d[i];printf("%lld",ans);return 0; }

轉載于:https://www.cnblogs.com/xydddd/p/5155279.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的差分约束 【bzoj2330】[SCOI2011]糖果的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。