自己怎么做免费网站,公司如何做自己的网站,鲅鱼圈网站制作,做的最好的微电影网站差点就忘了还有差分约束这个东西……看见了就要学习一个 原题#xff1a; 幼儿园里有N个小朋友#xff0c;lxhgww老师现在想要给这些小朋友们分配糖果#xff0c;要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心#xff0c;总是会提出一些要求#xff0c;比如小明不希…差点就忘了还有差分约束这个东西……看见了就要学习一个 原题 幼儿园里有N个小朋友lxhgww老师现在想要给这些小朋友们分配糖果要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心总是会提出一些要求比如小明不希望小红分到的糖果比他的多于是在分配糖果的时候lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的lxhgww想知道他至少需要准备多少个糖果才能使得每个小朋友都能够分到糖果并且满足小朋友们所有的要求。 N100000K1000001A, BN 差分约束模板题学习一个 以操作3为例如果a不少于b那么a-b0ab0 所以连b到a权值为0的边根据三角形不等式要跑最长路来使条件满足 具体原理我也想不太清楚反正记住搞出三角形不等式后跑符号相反的spfa就对了 _(:3 」∠)_ 因为写出了像q[tl]false酱sb的东西没对拍所以没1A…… 注意longlong 代码 1 #includeiostream2 #includecstdio3 #includealgorithm4 #includecstring5 #includecmath6 using namespace std;7 int rd(){int z0,mk1; char chgetchar();8 while(ch0||ch9){if(ch-)mk-1; chgetchar();}9 while(ch0ch9){z(z3)(z1)ch-0; chgetchar();}
10 return z*mk;
11 }
12 struct ddd{int nxt,y,v;}e[210000]; int lk[110000],ltp0;
13 inline void ist(int x,int y,int z){ e[ltp].nxtlk[x],lk[x]ltp,e[ltp].yy,e[ltp].vz;}
14 int n,m;
15 int dstc[110000],cnt[110000];
16 int q[110000],hd0,tl0,tp100001; bool vstd[110000];
17 bool spfa(){
18 memset(vstd,0,sizeof(vstd));
19 //memset(dstc,0,sizeof(dstc));
20 for(int i1;in;i) q[hd]i,dstc[i]1;
21 while(tl!hd){
22 tl(tltp ? 0 : tl1);
23 for(int ilk[q[tl]];i;ie[i].nxt)if(dstc[q[tl]]e[i].vdstc[e[i].y]){
24 dstc[e[i].y]dstc[q[tl]]e[i].v;
25 if(cnt[e[i].y]n) return false;
26 if(!vstd[e[i].y]) q[hd(hdtp ? 0 : hd1)]e[i].y,vstd[e[i].y]true;
27 }
28 vstd[q[tl]]false;
29 }
30 return true;
31 }
32 int main(){//freopen(ddd.in,r,stdin);
33 cinnm;
34 int mk,l,r;
35 while(m--){
36 mkrd(),lrd(),rrd();
37 if(mk1) ist(l,r,0),ist(r,l,0);
38 else if(mk2){
39 if(lr){ cout-1endl; return 0;}
40 ist(l,r,1);
41 }
42 else if(mk3) ist(r,l,0);
43 else if(mk4){
44 if(lr){ cout-1endl; return 0;}
45 ist(r,l,1);
46 }
47 else if(mk5) ist(l,r,0);
48 }
49 if(!spfa()){ cout-1endl; return 0;}
50 long long ans0;
51 for(int i1;in;i) ansdstc[i];
52 coutansendl;
53 return 0;
54 } View Code 转载于:https://www.cnblogs.com/JSL2018/p/6539363.html
