poj3169:Layout——差分约束+Bellman-Ford算法

2022/2/16 12:11:36

本文主要是介绍poj3169:Layout——差分约束+Bellman-Ford算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

差分约束系统

参考:https://www.cnblogs.com/genius777/p/9163103.html

差分约束系统只是对最短路算法的一种应用,没有什么新的算法,只是对于具体问题的建图方法的确定

差分约束系统解决的问题是不等式组的求解:

X1 - X2 <= 0
X1 - X5 <= -1
X2 - X5 <= 1
X3 - X1 <= 5
X4 - X1 <= 4
X4 - X3 <= -1
X5 - X3 <= -3
X5 - X4 <= -3

这就是一个不等式组,给出的不等式组只存在小于等于号,如果有个别的式子是大于等于,我们可以通过两边同时乘-1的得到统一的不等号方向的不等式组。

这个不等式组一定是无解和无数解两种情况,因为如果是存在任意一组解,{x1,x2,x3,x4,x5},我们都可以通过{x1+k,x2+k,x3+k,x4+k,x5+k}得到一个新的解。所以解的个数是无数的。

因为每个数都加k,他们任意两个数之间的差是不变的,所以对于不等式没有影响。

与最短路联系

B - A <= c     (1)
C - B <= a     (2)
C - A <= b     (3)

如果要求C-A的最大值,可以知道max(C-A)= min(b,a+c),而这正对应了下图中C到A的最短路。

img

差分约束建图技巧

1.对于一个全部都是<=号的不等式组,我们可以将每个式子转化为Xi<=Xj+W(i,j),那么就建一条边,Xj->Xi=W(i,j),然后利用最短路径解决问题,在x0定死的情况下,求得最小值

2.对于一个全部都是>=号的不等式组,我们可以将每个式子转化为Xi>=Xj+W(i,j),那么就建一条边,Xj->Xi=W(i,j),然后利用最长路径解决问题,在x0定死的情况下,求得最大值

如果dis[Xi]为inf或-inf,那么Xi为任意解

如果求最短路的过程中出现负环,那么说明该不等式组无解

题目描述

需要放置n头牛,AL和BL两头牛之间存在“喜欢”关系,则它们之间的距离不能超过DL,有些AD和BD两头牛之间存在“不喜欢”关系,则它们之间的距离不能超过DD。所有牛编号从1~N,求1号牛和N号牛之间的最大距离,无解输出-1,距离无限大输出-2

分析

根据条目分析,可以得出约束条件为,d[i]为第i头牛放置的位置

  • d[i+1] + 0 >= d[i],n头牛按编号顺序依次放置,且可放置在同一位置
  • d[AL] + DL >= d[BL],“喜欢”关系的两头牛之间距离不超过DL
  • d[BD] - DD >= d[AD],“不喜欢”关系两头牛之间的距离不小于DD

将原问题转化成最短路问题,

  • 建立一条从i+1到i,权值为0的边
  • 建立一条从AL到BL,权值为DL的边
  • 建立一条从BD到AD,权值为-DD的边

原问题d[N] - d[1]的最大值,对应顶点1到顶点N的最短距离(不理解可看上文差分约束与最短路径关系部分),由于图中存在负权重的边,不能使用Dijkstra算法,可采用Bellman-Ford算法求解。

代码

#include <stdio.h>
#include <iostream>
#include <climits>
#include <vector>
using namespace std;

const int MAXN = 1000 + 10;
const int MAXM = 10000 + 10;
const int INF = INT_MAX;

int N, ML, MD;
int AL[MAXM], BL[MAXM], DL[MAXM];   //'喜欢'关系约束
int AD[MAXM], BD[MAXM], DD[MAXM];   //'不喜欢'关系约束
int dist[MAXN];     //最短距离

//邻接表存储图
struct Edge{
    int to, weight;
    Edge(int t, int w): to(t), weight(w) {}
};
vector<Edge> G[MAXN];

//根据差分约束建立图
void BuildGraph(){
    //从i+1->i权值为0的边
    for (int i = 1; i < N; ++i) {
        G[i+1].push_back(Edge(i, 0));
    }

    /*
         * BL - AL <= DL
         * AL + DL >= BL
         * 从AL到BL权值为DL的边 */
    for (int i = 0; i < ML; ++i) {
        G[AL[i]].push_back(Edge(BL[i], DL[i]));
    }

    /*
         * BD - AD >= DD
         * BD - DD >= AD
         * 从BD到AD权值-DD的边*/
    for (int i = 0; i < MD; ++i) {
        G[BD[i]].push_back(Edge(AD[i], -DD[i]));
    }
}

void Bellman_Ford(){
    fill(dist, dist + MAXN, INF);
    dist[1] = 0;

    //循环N-1次
    for (int i = 0; i < N - 1; ++i) {
        //对所有边进行松弛操作
        for (int j = 1; j <= N; ++j) {
            for (int k = 0; k < G[j].size(); ++k) {
                Edge e = G[j][k];
                if (dist[j] < INF && dist[e.to] > dist[j] + e.weight){
                    dist[e.to] = dist[j] + e.weight;
                }
            }
        }
    }

    //再遍历一次所有边(第N次循环)
    bool ngloop = false;
    for (int j = 1; j <= N; ++j) {
        for (int k = 0; k < G[j].size(); ++k) {
            Edge e = G[j][k];
            //如果本次有更新,则存在负环
            if (dist[j] < INF && dist[e.to] > dist[j] + e.weight){
                dist[e.to] = dist[j] + e.weight;
                ngloop = true;
            }
        }
    }

    if (ngloop){
        printf("-1\n");
    }
    else{
        int ans = dist[N];
        if (ans == INF){
            ans = -2;
        }
        printf("%d\n", ans);
    }
}

int main(){
    scanf("%d%d%d", &N, &ML, &MD);
    for (int i = 0; i < ML; ++i) {
        scanf("%d%d%d", &AL[i], &BL[i], &DL[i]);
    }
    for (int i = 0; i < MD; ++i) {
        scanf("%d%d%d", &AD[i], &BD[i], &DD[i]);
    }

    BuildGraph();

    Bellman_Ford();

    return 0;
}


这篇关于poj3169:Layout——差分约束+Bellman-Ford算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程