POJ 3169 Layout （差分约束系统 + Bellman-ford算法）

Description

Input

Output

Sample Input

4 2 1
1 3 10
2 4 20
2 3 3

Sample Output

27

Hint

Source

题意：一个牛舍里有N头牛，有一些牛的关系比较好，他们希望彼此不超过一定的距离。当然也有些牛关系不好，他们希望彼此超过一定的距离。有ML对牛的关系比较好，并给出每对牛的所不超过的距离D；同样，有MD对牛的关系不好，并给出每对牛的所超过的距离D。问是否有满足这样的安排方案满足所有牛的要求。若不存在，输出-1；若存在，但是牛1和牛N之间的距离可以任意大，输出-2；否则，输出牛1和牛N之间的最大距离。

解析：记第i号牛的位置是d[i]，首先，牛市按照编号顺序排的，所以有d[i] <= d[i+1]成立。其次，对于关系好的牛的最大距离限制有d[AL] + DL >= d[BL]，同样对于关系不好的牛的最小距离限制有d[AD] + DD <= d[BD]。这样，原来的问题就可以转化为在满足着三个不等式组的情况下，求解d[N] - d[1]的最大值问题。当然可以用线性规划的方法去解决。但是这道题还可以更简单的求解。这个可以抽象为一个无向图，各个牛为顶点，他们之间的好或不好的关系为边，限制的距离作为边尚德权值。这样可以将这三个不等式转化一下：d[i+1] + 0 >= d[i]表示从i+1到i连一条权值为0的边，d[AL] + DL >= d[BL]表示从AL到BL连一条权值为DL的边，d[BD] - DD >= d[AD]表示从BD到AD连一条权值为-DD的边。所求d[N] - d[1]的最大值，对应于d[1]到d[n]之间的最短路径。由于存在负权边，所以用bellman-ford算法。

AC代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
#define INF 123456789
#define LL long long
#define MID(a, b)  a+(b-a)/2
const int maxn = 1000 + 10;
const int maxm = 10000 + 10;

int al[maxm], bl[maxm], dl[maxm];
int ad[maxm], bd[maxm], dd[maxm];
int d[maxn];
int N, ML, MD;

void solve(){
    fill(d, d+N, INF);             //初始化d[]
    d[0] = 0;

    for(int i=0; i<N; i++){
        for(int j=0; j+1<N; j++)          //检查d[j]能否通过d[j+1]松弛
            if(d[j+1] < INF) d[j] = min(d[j], d[j+1] + 0);

        for(int j=0; j<ML; j++)           //检查d[BL]能否通过d[AL]松弛
            if(d[ al[j] - 1 ] < INF) d[ bl[j] - 1 ] = min(d[ bl[j] - 1 ], d[ al[j] - 1 ] + dl[j]);

        for(int j=0; j<MD; j++)           //检查d[AD]能否通过d[BD]松弛
            if(d[ bd[j] - 1 ] < INF) d[ ad[j] - 1 ] = min(d[ ad[j] - 1 ], d[ bd[j] - 1 ] - dd[j]);
    }

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

int main(){
    #ifdef sxk
        freopen("in.txt", "r", stdin);
    #endif // sxk

    while(scanf("%d%d%d", &N, &ML, &MD)!=EOF){
        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]);
        solve();
    }
    return 0;
}

POJ 3169 Layout （差分约束系统 + Bellman-ford算法）

原文：http://blog.csdn.net/u013446688/article/details/43279887