频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
hdu1384 poj1202 Intervals --- 差分约束
2014-04-26 11:06:49         来源: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-yx-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]

点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:NYOJ 127 星际之门(一)
下一篇:hdu 1286 找新朋友 (欧拉函数)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站