本文主要是介绍hdu1384 poj1202 Intervals --- 差分约束，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
差分约束系统
差分约束系统的应用难点在于将实际问题转换为差分约束系统。
简单来说，要构造出一系列满足题意的不等式 形如 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<k =>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 <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#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);//求最长路 赋值为0memset(inq,0,sizeof inq);// memset(outq,0,sizeof outq);queue<int> 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]<d[x]+e[i].w){d[e[i].v]=d[x]+e[i].w;if(!inq[e[i].v]){inq[e[i].v]=1;q.push(e[i].v);}}}if(x>minn&&d[x-1]<d[x]-1){d[x-1]=d[x]-1;if(!inq[x-1]){inq[x-1]=1;q.push(x-1);}}if(x<maxx&&d[x+1]<d[x]){d[x+1]=d[x];if(!inq[x+1]){inq[x+1]=1;q.push(x+1);}}}
}int main()
{int a,b,c;while(~scanf("%d",&n)){init();//又忘了这个maxx=-1;minn=inf;for(int i=0;i<n;i++){scanf("%d%d%d",&a,&b,&c);addedge(a,++b,c);maxx=max(maxx,b);minn=min(minn,a);}spfa();printf("%d\n",d[maxx]);}return 0;
}
这篇关于hdu1384 poj1202 Intervals --- 差分约束的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
