首页 > 代码库 > 差分约束系统 初见
差分约束系统 初见
今天初次学习差分约束系统，很神奇的东西
定义：
一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号为1…n。每个块的大小为一个单位尺寸并最多可种一裸树。每个居民想在门前种些树并指定了三个号码b，e，t。这三个数表示该居民想在b和e之间最少种t棵树。当然，b≤e，居民必须保证在指定地区不能种多于地区被分割成块数的树，即要求T≤ e-b+1。允许居民想种树的各自区域可以交叉。出于资金短缺的原因，环保部门请你求出能够满足所有居民的要求，需要种树的最少数量。
思路：可以将这个题目借助前缀和数组转化到一系列的不等式关系。若用f[i]表示到i所用的树木数，f[e]-f[b]>=t（建一条从b到e的长度为t的边权），在题目中还有一个隐含条件，就是0<=f[i]-f[i-1]<=1，这个隐含关系中可以将f[i]与f[i-1]与0、1建立关系，又多了很多条边。对于<=的情况可以同时乘-1，就转变成了>=，进而用最长路求最小值。
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int next[1000000]={0},point[30001]={0},en[1000000]={0},va[1000000]={0},dis[30001]={0},que[1000001]={0};bool visit[30001]={false};int main(){ int i,j,n,h,b,e,t,tot=0,head,tail,y,x; scanf("%d%d",&n,&h); for (i=1;i<=h;++i) { scanf("%d%d%d",&b,&e,&t); --b; ++tot; next[tot]=point[b]; point[b]=tot; en[tot]=e; va[tot]=t; } for (i=1;i<=n;++i) { ++tot; next[tot]=point[i-1]; point[i-1]=tot; en[tot]=i; va[tot]=0; ++tot; next[tot]=point[i]; point[i]=tot; en[tot]=i-1; va[tot]=-1; } memset(dis,128,sizeof(dis)); dis[0]=0;head=0;tail=1; visit[0]=true;que[1]=0; do{ head=head%1000000+1; x=que[head]; visit[x]=false; y=point[x]; while (y!=0) { if (dis[x]+va[y]>dis[en[y]]) { dis[en[y]]=dis[x]+va[y]; if (!visit[en[y]]) { visit[en[y]]=true; tail=tail%1000000+1; que[tail]=en[y]; } } y=next[y]; } }while(head!=tail); printf("%d\n",dis[n]);}
CODEVS1768种树3
为了绿化乡村，H村积极响应号召，开始种树了。
H村里有n幢房屋，这些屋子的排列顺序很有特点，在一条直线上。于是方便起见，我们给它们标上1~n。树就种在房子前面的空地上。
同时，村民们向村长提出了m个意见，每个意见都是按如下格式：希望第li个房子到第ri个房子的房前至少有ci棵树。
因为每个房屋前的空地面积有限，所以每个房屋前最多只能种ki棵树。
村长希望在满足村民全部要求的同时，种最少的树以节约资金。请你帮助村长。
思路：和上一题的大致思路一样，不过有一点不同，0<=f[i]-f[i-1]<=k[i]，其他都相同。
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int next[5000000]={0},point[500001]={0},en[5000000]={0},va[5000000]={0},k[500001]={0},que[10000001]={0};long long dis[500001]={0};bool visit[500001]={false};int main(){ int i,j,n,m,lp,rp,cp,head,tail,tot=0,x,y; scanf("%d%d",&n,&m); for (i=1;i<=n;++i) scanf("%d",&k[i]); for (i=1;i<=m;++i) { scanf("%d%d%d",&lp,&rp,&cp); --lp; ++tot; next[tot]=point[lp]; point[lp]=tot; en[tot]=rp; va[tot]=cp; } for (i=1;i<=n;++i) { ++tot; next[tot]=point[i-1]; point[i-1]=tot; en[tot]=i; va[tot]=0; ++tot; next[tot]=point[i]; point[i]=tot; en[tot]=i-1; va[tot]=-k[i]; } head=0;tail=1;que[1]=0; memset(dis,128,sizeof(dis)); dis[0]=0;visit[0]=true; do{ head=head%10000000+1; x=que[head]; visit[x]=false; y=point[x]; while(y!=0) { if (dis[x]+va[y]>dis[en[y]]) { dis[en[y]]=dis[x]+va[y]; if (!visit[en[y]]) { visit[en[y]]=true; tail=tail%10000000+1; que[tail]=en[y]; } } y=next[y]; } }while(head!=tail); printf("%lld\n",dis[n]);}
poj3159Candies
题目大意：已知a、b两名小朋友间的差值关系（b-a<=c），求n-1的最大值。
思路：又变成了赤裸裸的差分约束系统，a到b的边权为c，搜最短路就可以了。但是这个题的数据卡spfa+queue，从网上学习到spfa可以用栈实现，于是就ac了。（太长知识了，从不知道stack可以实现spfa。。。）
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int next[3000000]={0},point[300001]={0},en[3000000]={0},va[3000000]={0},que[1000001]={0};long long dis[300001]={0};bool visit[300001]={false};int main(){ int i,j,n,m,tot=0,a,b,c,top=0,x,y; scanf("%d%d",&n,&m); for (i=1;i<=m;++i) { scanf("%d%d%d",&a,&b,&c); ++tot; next[tot]=point[a]; point[a]=tot; en[tot]=b; va[tot]=c; } top=1;que[1]=1;visit[1]=true; memset(dis,127,sizeof(dis));dis[1]=0; while(top>0) { x=que[top]; --top; visit[x]=false; y=point[x]; while(y!=0) { if (dis[en[y]]>dis[x]+va[y]) { dis[en[y]]=dis[x]+va[y]; if (!visit[en[y]]) { visit[en[y]]=true; ++top; que[top]=en[y]; } } y=next[y]; } } printf("%lld\n",dis[n]);}
在今后的学习中可能还会遇到大于或小于的情况，都可以通过所谓的常数（通常是右侧的部分）+1\-1来转化为>=\<=。
通常情况下最好用spfa，还要判断负环，有的话就不存在。
对于不等式的选取和转化可能是一个难点，但真正能找出题目的本意，正确的套用差分约束系统，才是重点和难点。多加练习吧！！！
差分约束系统 初见