热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

差分约束系统求解HouseMan跳跃问题的思路与方法

本文讨论了使用差分约束系统求解HouseMan跳跃问题的思路与方法。给定一组不同高度,要求从最低点跳跃到最高点,每次跳跃的距离不超过D,并且不能改变给定的顺序。通过建立差分约束系统,将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法,并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。

题意:给个n个不同的高度,一个人从最低点跳跃,每次可以跳到第一个比它高的位置,最后跳到最高点,然后每次最多可以跳的距离为D,而且在跳跃时可以在不改变给定顺序的情况下移动这些高度,使得最后起始点和终点的位置最远,
思路:自己想了一会,想的方向错了,我自己想的方法是将最小高度记为0,最大高度记为n-1,然后写查分约束方程,这了一会发现条件不足,没想法了,看了大牛们的解法发现原来以给定的顺序直接进行条件就可以了,而且好简单,因为我们不能调整给定的顺序,那么对于给定的顺序就可以有pos(i+1)>=pos(i)+1,那么可以写出一个条件就是i+1–>i连一条权值为-1的边,还有一个条件是相邻两个要跳跃的距离不可以大于D,可以写出另一个方程,而现在条件全部是基于给定的序列,那么剩下的条件也要在这个基础进行,右面的点一定是在左边的点的后面,那么式子也就很好列出来了,图建完了,查询距离就用SPFA判环并输出就行了,有一点小问题就是建边的方向和跳跃的方向不同,我们要保证是向一个方向建图的,为什么这样呢,比如举个栗子,与例1类似,4 4,10 30 20 40这组的话10到20,跳跃的顺序是10 20 30 40,但是如果也是按照这个顺序建边的话,那么你将无法知道10的右面是谁到底是20还是30,找不到既定的顺序,所以只能这样建边,那么随之而来的问题就是,1和n的位置关系,如果1在n的左面那么肯定是从1到n跑spfa,因为我是从左到右建边的,1在n右面的话,也就是从n到1跑最短路了,这块要注意一下

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn=1010;
const int INF=0x3f3f3f3f;
struct sa
{
    int val;
    int id;
} a[maxn];
int cmp(sa x,sa y)
{
    return x.valstruct EdgeNode
{
    int to;
    int w;
    int next;
};
EdgeNode edges[maxn*maxn];
int N,M;
int head[maxn],edge;
bool vis[maxn];
queue<int>que;
int dis[maxn],cnt[maxn];
void addedge(int u,int v,int c)
{
    edges[edge].w=c;
    edges[edge].to=v;
    edges[edge].next=head[u];
    head[u]=edge++;
}
void init()
{
    memset(a,0,sizeof(a));
    memset(cnt,0,sizeof(cnt));
    memset(vis,0,sizeof(vis));
    memset(dis,0,sizeof(dis));
    memset(head,-1,sizeof(head));
    edge=0;
}
bool spfa(int s,int n)
{
    int u;
    for(int i=0; i<=n; i++)
        dis[i]=INF;
    memset(vis,0,sizeof(vis));
    while(!que.empty())
        que.pop();
    que.push(s);
    vis[s]=true;
    dis[s]=0;
    memset(cnt,0,sizeof(cnt));
    cnt[s]=1;
    while(!que.empty())
    {
        u=que.front();
        que.pop();
        vis[u]=false;
        for(int i=head[u]; i!=-1; i=edges[i].next)
        {
            int v=edges[i].to;
            int w=edges[i].w;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(!vis[v])
                {
                    vis[v]=true;
                    que.push(v);
                    if(++cnt[v]>=n)
                        return false;
                }
            }
        }
    }
    return true;
}
int main()
{
    int T,n,d;
    cin>>T;
    int Case=0;
    while(T--)
    {
        init();
        cin>>n>>d;
        for(int i=1; i<=n; i++)
        {
            cin>>a[i].val;
            a[i].id=i;

        }
        for(int i=1;i1,i,-1);
        sort(a+1,a+1+n,cmp);
        for(int i=1; i//addedge(i+1,i,-1);
            if(a[i].id1].id)
                addedge(a[i].id,a[i+1].id,d);
            else
                addedge(a[i+1].id,a[i].id,d);//只能从一个方向往另一个方向加边
        }
        cout<<"Case "<<++Case<<": ";
        bool flag=1;
        int first, second;

        if(a[1].id1].id;
            secOnd=a[n].id;
        }
        else
           {
               first=a[n].id;
               secOnd=a[1].id;
           }
           flag=spfa(first,n);
        if(flag==false)
            cout<<-1<else
        {
            cout<//这里要输出的是n到1的距离,但是second不能换成n,因为排过序了,n不一定是原来的顺序,所以要用id,这块也要注意一下
        }
    }
    return 0;
}

推荐阅读
author-avatar
desn
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有