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

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

你的工作是:如果不存在满足要求的方案,输出-1;如果1号奶牛和N号

奶牛间的距离可以任意大,输出-2;否则,计算出在满足所有要求的情况下,1号奶牛和N号奶牛间可能的最大距离。

输入描述 Input Description
Line 1: Three space-separated integers: N, ML, and MD.

Lines 2..ML+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at most D (1 <= D <= 1,000,000) apart.

Lines ML+2..ML+MD+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at least D (1 <= D <= 1,000,000) apart.

输出描述 Output Description
Line 1: A single integer. If no line-up is possible, output -1. If cows 1 and N can be arbitrarily far apart, output -2. Otherwise output the greatest possible distance between cows 1 and N.

样例输入 Sample Input

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

样例输出 Sample Output
27

题解:
这个题目看描述就是一系列的不等式,所以很自然的想到是差分约束系统。嗯,什么是差分约束系统呢?
简单的说就是将一系列不等式转化为一条条边然后跑最短路。
那么怎么转化呢?
若问题是像本题一样一个点到各个点的最大距离

可以将题目中的条件写成如下形式

xj−xi≤D        //两个点距离小于D
xj−xi≥D        //两个点距离大于D

我们对于第一个不等式作如下转化

    xj − xi ≤ D        
=> xj ≤ xi + D 

发现它和最短路问题中的三角不等式是一致的:

//D是S到V的最短路 C是U到V的边权
D(s,v)≤D(s,u)+C(u,v),(u,v)∈E

于是我们可以将

xj ≤ xi + D 这个不等式转化为
由i到j的一条长度为D的边
xj − D ≥ xi 这个不等式转化为
由j到i的一条长度为-D的边

详细证明请看:chrt
然后由1作为起点跑SPFA(必须为SPFA因为dij在有负边的时候不能使用)
对于题目:若有负权环则输出-1,若无法到达点N则输出-2,否则直接输出1~N的距离即可
判断负环
有一种较优秀的方法:对于每一个点记录从起点到这个点最短路径包含的边的条数。
若边的条数大于N,易证这个图有负环。
代码

/*
作者:WZH
题目:p1242 布局
*/
#include <iostream>
#include <cstdio>
#include <queue>

const int MAXN = 1005,MAXX = 100000,INF = 10e8;

using namespace std;

int N,ML,MD,e = 1,head[MAXN],sum[MAXN],d[MAXN];
bool inq[MAXN];

queue<int>q; 

struct node{
    int v,c,next;
}edge[MAXX];

inline int read(){
    int x = 0;char ch = getchar();
    while(ch < '0' || '9' < ch) {ch = getchar();}
    while('0' <= ch&&ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}
    return x;
}

inline void addedge(int u,int v,int c){
    edge[e] = (node){v,c,head[u]};head[u] = e++;
}

inline void init(){
    N = read();ML = read();MD = read();
    
    int u,v,c;
    
    for(int i = 1;i <= ML;i++){
        u = read();v = read();c = read();
        addedge(u,v,c);
    }
    
    for(int i = 1;i <= MD;i++){
        u = read();v = read();c = read();
        addedge(v,u,-c);
    }
} 

inline int spfa()
{
    for(int i = 1;i <= N;i++) d[i] = INF;
    
    q.push(1);inq[1] = true;
    d[1] = 0;sum[1] = 1;
    
    while(!q.empty()){
        int u = q.front();q.pop();inq[u] = false;
        
        for(int i = head[u];i;i = edge[i].next){
            int v = edge[i].v,c = edge[i].c;
            if(d[v] > d[u] + c){
                d[v] = d[u] + c;
                sum[v] = sum[u] + 1;
                if(!inq[v]) {q.push(v);inq[v] = true;}
                if(sum[v] > N) return -1;
            }
        }
    }
    
    if(d[N] == INF) return -2;
    return d[N];
}

int main()
{
    init();
    
    printf("%d",spfa());
    
    return 0;
}
Last modification:October 1st, 2018 at 08:22 am
If you think my article is useful to you, please feel free to appreciate