首页 > 代码库 > BZOJ2330: [SCOI2011]糖果

BZOJ2330: [SCOI2011]糖果

2024-07-17 11:33:14   218人阅读

2330: [SCOI2011]糖果

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 2220  Solved: 610
[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

Sample Output


11

HINT

 

【数据范围】


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


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


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

 

Source

Day1

题解：
本题是比较明显的查分约束系统，但我由于没有写过，所以这次好好写了些。
首先求最长路或最短路应该搞清，不过这是可以互相转化的，固定了写一种也许更好？
其次就是spfa写的时候发现了模版一个错误，如果用循环队列的话，终止条件是 l=r 而不是 l>=r
最后就是数据有点儿SXBK，第五个点是全为2 or 4，而且数据用肉眼看出来是1<2<3<4<......100000，
但它在描述的时候一会是前一个<后一个，一会是后一个>前一个，导致每次的spfa更新不了几个点
但如果最后连0的边的时候 for i=n downtown 1 do 的或就可以过了，否则就被卡爆了
还有就是spfa判环的方法，最短路判负环，最长路判正环，都是新增一个数组c表示0 - c 经过了几个点，如果c>当前总点数，一定是有环了
代码：
 1 const maxn=1000000+1000;maxm=1000000+1000; 2 type node=record 3      go,next,w:longint; 4      end; 5 var head,q,c:array[0..maxn] of longint; 6     d:array[0..maxn] of int64; 7     v:array[0..maxn] of boolean; 8     e:array[0..maxm] of node; 9     i,n,m,ch,x,y,tot:longint;10     ans:int64;11 procedure insert(x,y,z:longint);12  begin13    inc(tot);14    e[tot].go:=y;e[tot].w:=z;e[tot].next:=head[x];head[x]:=tot;15  end;16 function spfa:boolean;17  var i,x,y,l,r:longint;18    begin19      fillchar(d,sizeof(d),0);20      fillchar(v,sizeof(v),false);21      fillchar(c,sizeof(c),0);22      l:=0;r:=1;q[1]:=0;d[0]:=0;v[0]:=true;23      while l<>r do24       begin25        l:=l mod maxn+1;26        x:=q[l];v[x]:=false;27        i:=head[x];28        while i<>0 do29          begin30           y:=e[i].go;31           if d[x]+e[i].w>d[y] then32             begin33               d[y]:=d[x]+e[i].w;34               c[y]:=c[x]+1;35               if c[y]>n+1 then exit(false);36               if not(v[y]) then37                 begin38                   v[y]:=true;39                   r:=r mod maxn+1;40                   q[r]:=y;41                 end;42             end;43           i:=e[i].next;44          end;45       end;46    exit(true);47    end;48 function init:boolean;49  begin50    readln(n,m);51    for i:=1 to m do52     begin53       readln(ch,x,y);54       if (x=y) and (ch and 1=0) then begin writeln(‘-1‘);exit(false);end;55       case ch of56       1:begin insert(x,y,0);insert(y,x,0);end;57       2:insert(x,y,1);58       3:insert(y,x,0);59       4:insert(y,x,1);60       5:insert(x,y,0);61       end;62     end;63    for i:=n downto 1 do insert(0,i,1);64    exit(true);65  end;66 procedure main;67  begin68    if not(spfa) then writeln(‘-1‘)69    else70      begin71        ans:=0;72       // for i:=1 to n do writeln(i,‘ ‘,d[i],‘ ‘,c[i]);73        for i:=1 to n do inc(ans,d[i]);74        writeln(ans);75      end;76  end;77 78 begin79  assign(input,‘input.txt‘);assign(output,‘output.txt‘);80  reset(input);rewrite(output);81  if init then main;82  close(input);close(output);83 end.
View Code

 


联系
我们