「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
11
HINT
「数据范围」
对于30%的数据，保证 N<=100
对于100%的数据，保证 N<=100000
对于所有的数据，保证 K<=100000，1<=X<=5，1<=A, B<=N
题解
差分约束系统自己百度
有一个坑爹的点就是形成的是十万个点的一条链，如果从0到所有点顺序加边就会T，改成倒序就AC
最好是直接把所有点放入队列
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include<iostream> #include<cstdio> #define N 100005 using namespace std; int n,k,cnt,q[N],head[N],cir[N],dis[N]; long long ans; bool inq[N]; struct data{int to,next,v;}e[4*N]; void insert(int u,int v,int w){e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;} bool spfa() { int t=0,w=1,now; q[0]=0;inq[0]=1;cir[0]=1; while(t!=w) { now=q[t];t++;if(t==N)t=0; for(int i=head[now];i;i=e[i].next) { if(dis[now]+e[i].v>dis[e[i].to]) { dis[e[i].to]=dis[now]+e[i].v; if(++cir[e[i].to]>=n)return 0; if(!inq[e[i].to]) { inq[e[i].to]=1;q[w++]=e[i].to; if(w==N)w=0; } } } inq[now]=0; } return 1; } int main() { scanf("%d%d",&n,&k);int x,a,b; while(k--) { scanf("%d%d%d",&x,&a,&b); switch(x) { case 1:insert(a,b,0);insert(b,a,0);break; case 2:if(a==b){printf("-1");return 0;} insert(a,b,1);break; case 3:insert(b,a,0);break; case 4:if(a==b){printf("-1");return 0;} insert(b,a,1);break; case 5:insert(a,b,0);break; } } for(int i=n;i>0;i--)insert(0,i,1); if(!spfa()){printf("-1");return 0;} for(int i=1;i<=n;i++)ans+=dis[i]; printf("%lld",ans); return 0; } |
计数器 9320613
OI 课件=>
OI 课件=>
数据的良心何在，我被你讲的那个店坑了一晚上，一直以为我的spfa写错了，尴尬
输入2 1 2 1 2输出-1
貌似设了0点后判圈那里应该是>n？