hdu1384 poj1202 Intervals --- 差分约束 - c++编程基础

差分约束系统

差分约束系统的应用难点在于将实际问题转换为差分约束系统。

简单来说，要构造出一系列满足题意的不等式形如 Si-Sj<=Ck，且必须含等号。

对于每一个这样的不等式，构造有向边 w(j->i)=Ck。

为保证图的连通，我们引入附加结点Vs。初始化w(s->i)=0，d[Vs]=0

接下来就是求解源点到其他点的单源最短路径。

由于差分约束系统中通常含负值，所以我们一般用spfa或者bellman来求最短路径。

这里有个技巧，不想要添加附加结点的话，可以开始将所有点加入队列，相当于Vs入队，接下来的更新没有指回Vs的结点，所以可以省略。

注意点:
1. 如果要求最大值想办法把每个不等式变为标准x-y<=k的形式,然后建立一条从y到x权值为k的边,变得时候注意x-y x-y<=k-1
如果要求最小值的话,变为x-y>=k的标准形式，然后建立一条从y到x的k边，求出最长路径即可
2.如果权值为正，用dj，spfa，bellman都可以，如果为负不能用dj，并且需要判断是否有负环，有的话就不存在

---------------回到这道题--------------

题意：

构造一个集合，要求对每一个给定的区间 [a, b]，至少包含其中的n个数

求满足条件的集合内最少含多少个数。

思路：

令Si表示在[0,i-1]区间内要选多少个数。则可列出不等式：

S(b+1)-Sa>=C

另外，由于一个数至多取一个，至少取0个，则有：

0=< Si-S(i-1)<=1

根据以上不等式构图，以给定区间的最小值为起点，最大值为终点，求解最长路即可。

小结：

其实不等式就可以看成图中边权需要满足的条件，将所有不满足条件的边更新就是了。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #define inf 0x3f3f3f3f #define ll long long #define mod 1000000007 using namespace std; struct node { int v,w,next; }e[50010]; int d[50010],head[50010],inq[50010],n,h,minn,maxx; void init() { memset(head,-1,sizeof head); h=0; } void addedge(int a,int b,int c) { e[h].v=b; e[h].w=c; e[h].next=head[a]; head[a]=h++; } void spfa() { memset(d,0,sizeof d);//求最长路 赋值为0 memset(inq,0,sizeof inq); // memset(outq,0,sizeof outq); queue
           
             q; //省略掉那个虚点,可以优化spfa.虚点作用是让所有点入队 //所以省略掉这点的话,需要手动把所有点入队 for(int i=minn;i<=maxx;i++) { q.push(i); inq[i]=1; } d[minn]=0; while(!q.empty()) { int x=q.front(); q.pop(); inq[x]=0; // outq[x]++; // if(outq[x]>n) return -1;//存在负环//此题不存在 for(int i=head[x];i!=-1;i=e[i].next) { if(d[e[i].v]
            
             minn&&d[x-1]