首页 > 代码库 > PKU 3169 Layout(差分约束系统+Bellman Ford)

PKU 3169 Layout(差分约束系统+Bellman Ford)

2024-09-05 09:12:48   218人阅读

题目大意：原题链接

当排队等候喂食时，奶牛喜欢和它们的朋友站得靠近些。FJ有N（2<=N<=1000）头奶牛，编号从1到N，沿一条直线站着等候喂食。奶牛排在队伍中的顺序和它们的编号是相同的。因为奶牛相当苗条，所以可能有两头或者更多奶牛站在同一位置上(即间距可能为0)。即是说，如果我们想象奶牛是站在一条数轴上的话，允许有两头或更多奶牛拥有相同的横坐标。

一些奶牛相互间存有好感，它们希望两者之间的距离不超过一个给定的数L。另一方面，一些奶牛相互间非常反感，它们希望两者间的距离不小于一个给定的数D。给出ML条关于两头奶牛间有好感的描述，再给出MD条关于两头奶牛间存有反感的描述。（1<=ML,MD<=10000，1<=L,D<=1000000）

你的工作是：如果不存在满足要求的方案，输出-1；如果1号奶牛和N号奶牛间的距离可以任意大，输出-2；否则，计算出在满足所有要求的情况下，1号奶牛和N号奶牛间可能的最大距离。

解题思路：参考链接

先介绍一下负权回路：在一个图里每条边都有一个权值（有正有负)

如果存在一个环（从某个点出发又回到自己的路径），而且这个环上所有权值之和是负数，那这就是一个负权环，也叫负权回路。

存在负权回路的图是不能求两点间最短路的，因为只要在负权回路上不断兜圈子，所得的最短路长度可以任意小。

 

对于任意i号奶牛，1<=i<=N，在距离上应该满足：d[i+1]-d[i]>=0

对于每个好感的描述(i,j,w),假设i<=j,体现到距离上的要求就是：d[j]-d[i]<=w

对于每个反感的描述(i,j,w),假设i<=j,体现到距离上的要求就是：d[j]-d[i]>=w

写成我们约定的形式：d[i+1]-d[i]>=0 ;d[j]-d[i]<=w ;d[j]-d[i]>=w

1.(假设v>u),则对于差分不等式v-u<=w,建一条u到v的权值为w的边,求的是最短路,得到的是最大值(本题求的就是最大值);

对于不等式 u-v>=w,建一条从v到u的权值为-w的边,求的是最长路,得到的是最小值。//保持方向一致,始终从1指向N

2.如果进行n-1次更新结束后仍然检测到负环,那么无解。

3.如果进行n-1次更新结束后d[n]没有更新,那么可以是任意解。

题目中的相邻点距为① -7->② -3->③ -17->④便是答案,完全符合题目要求

 

#include<cstdio>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
struct node
{
    int u,v;
    int w;
}edge[20010];
int n,m;
int tot=0,d[1010];

void Add(int u,int v,int w)
{
    edge[tot].u=u;
    edge[tot].v=v;
    edge[tot++].w=w;
}
int Bellman_Ford()
{
    for(int i=1;i<=n;i++) 
        d[i]=inf;
    d[1]=0;
    for(int i=1;i<n;i++){
        for(int j=0;j<m;j++){
            int u=edge[j].u;
            int v=edge[j].v;
            int w=edge[j].w;
            if(d[u]<inf&&d[u]+w<d[v])
                d[v]=d[u]+w;
        }
    }
    for(int j=0;j<m;j++){//检测负环
        int u=edge[j].u;
        int v=edge[j].v;
        int w=edge[j].w;
        if(d[u]<inf&&d[u]+w<d[v])
            return 0;
    }
    return 1;
}

int main(){
    int ml,md,u,v,w;
    scanf("%d%d%d",&n,&ml,&md);
    m=ml+md;
    for(int i=0;i<ml;i++){
        scanf("%d%d%d",&u,&v,&w);
        if(u>v) swap(u,v);//保持方向一致,始终从1指向N 
        Add(u,v,w);
    }//好感d[v]-d[u]<=w
    for(int i=0;i<md;i++){
        scanf("%d%d%d",&u,&v,&w);
        if(u>v) swap(u,v);
        Add(v,u,-w);
    }//反感d[v]-d[u]>=w
    if(!Bellman_Ford()) printf("-1\n");
    else if(d[n]==inf) printf("-2\n");
    else printf("%d\n",d[n]);
}

 

PKU 3169 Layout(差分约束系统+Bellman Ford)


联系
我们