POJ 1062 【带约束的最短路问题】

中文题题意不写。

建图：

我自己想到的建图方式是把每个物品看作两个点，编号分别是i和i+n，然后每个物品两个点之间边的权值是物品本身的价值。然后从第i个点往外连边，目标是可替代品顶点编号较小的点，权值为替代之后的优惠费用，然后将可替代品的顶点编号较大的点连向第i+n个顶点，权值是0.

这种建图方法将点的数量增加为原来的两倍，边的数量也相应增加，所以并不是好的建图方法。

大牛的建图方法是把旅行家看作是一个顶点，边的出路是每个物品，权值是每个物品对应的价值，然后当有物品可以有替代物品的时候，连边，起点是替代物，终点是被替代物品，权值是替代后的优惠价格。

这种建图方法更加稠密，同时节点的数量也少。

这道题需要注意的是连接是单向边。

对于约束的处理是，参考了大牛的思想。从第一个节点枚举到第n个节点，以该节点的等级为最低等级，以该节点加m为最高等级，将在这个范围以外的顶点做vis=1的处理，反复进行最短路，取这些最短路的最小值。

#include<stdio.h>

#include<string.h>

int max(int a,int b)

{

    if(a>b)

        return a;

    return b;

}

int min(int a,int b)

{

    if(a<b)

        return a;

    return b;

}

int m,n;

int dis[];

bool vis[];

const int inf=;

int deg[];

int ednum;

struct edge

{

    int id,w;

    edge *next;

};

edge *adj[];

edge edges[];

inline void addEdge(int a,int b,int c)

{

    edge *tmp;

    tmp=&edges[ednum];

    ednum++;

    tmp->id=b;

    tmp->w=c;

    tmp->next=adj[a];

    adj[a]=tmp;

}

void solve(int pos)

{

    vis[pos]=;

    for(edge *p=adj[pos]; p; p=p->next)

    {

        if((!vis[p->id]))

        {

            if((p->w)+dis[pos]<dis[p->id])

            {

                dis[p->id]=(p->w)+dis[pos];

            }

        }

    }

    int next=inf;

    int minn=inf;

    for(int i=; i<=*n; i++)

    {

        if(!vis[i]&&minn>dis[i])

        {

            minn=dis[i];

            next=i;

        }

    }

    if(next<=*n)

    {

        solve(next);

    }

}

int main()

{

    int num,id,tmon,up,low;

    int aa,bb,cc,dd;

    int rel=inf;

    scanf("%d%d",&m,&n);

    for(int i=; i<=n; i++)

    {

        scanf("%d%d%d",&aa,&bb,&cc);

        addEdge(i,i+n,aa);

        deg[i]=deg[i+n]=bb;

        for(int  j=; j<=cc; j++)

        {

            scanf("%d%d",&id,&tmon);

            addEdge(i,id,tmon);

            addEdge(id+n,i+n,);

        }

    }

    for(int i=; i<=n; i++)

    {

        for(int j=; j<=*n; j++)

        {

            dis[j]=inf;

        }

        for(int j=; j<=*n; j++)

        {

            if(deg[j]>=deg[i]&&deg[j]<=deg[i]+m)

            {

                vis[j]=;

            }

            else

            {

                vis[j]=;

            }

        }

        dis[]=;

        solve();

        if(rel>dis[+n])

            rel=dis[+n];

    }

    printf("%d\n",rel);

    return ;

}

巴特西

POJ 1062 【带约束的最短路问题】

最新文章

热门文章