[差分约束]糖果-白红宇

[差分约束]糖果

阅读量：5239 次

发布时间：2019-06-14

本文共 1201 字，大约阅读时间需要 4 分钟。

幼儿园里有N个小朋友，lxhgww老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的，lxhgww想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。

经典题目；

值得吐槽的是，数据里有一个10w个点的链，已被T成狗......

只有正向从n到1向起点连边才能过；

还有一种方法是最开始就把所有点放队列里；

通过率下降2个百分点；

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
               10 #include
               11 #include
                
                 12 using namespace std;13 #define FILE "dealing"14 #define LL long long15 #define up(i,j,n) for(int i=j;i<=n;i++)16 #define pii pair< int , int >17 #define abs(x) (x)<0?-(x):(x)18 namespace IO{19 char buf[1<<15],*fs,*ft;20 int gc(){ return fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft),fs==ft?-1:*fs++;}21 int read(){22 int x=0,ch=gc(),f=0;23 while(ch<'0'||ch>'9'){ if(ch=='-')f=1;ch=gc();}24 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();}25 return f?-x:x;26 }27 }using namespace IO;28 bool chkmin(int &a,int b){ return a>b?a=b,true:false;}29 bool chkmax(int &a,int b){ return a

View Code

转载于:https://www.cnblogs.com/chadinblog/p/6067092.html

你可能感兴趣的文章