题目大意:有 n 头牛 ,他们站成一条线,假设这条线是一条数轴,第 i 头牛所站的位置为 Si ,则首先必须满足如下条件:
1、对于所有的 i ( 2 <= i <= n), Si - S(i - 1) >= 0
然后又有ML 个条件:
Sb - Sa <= c
和MD个条件:
Sb - Sa >= c —> Sa - Sb <= -c
最后求出Sn - S1 的最大值。
解题思路:这是一道典型的差分约束,以 S1 为原点 ,求到点 Sn 的最小距离,此题关键在于判断是否存在权值为负数的环 ,以及 判断dis[ Sn ] 是否等于 无穷大。
请看程序:
#include <iostream> #include <set> #include <algorithm> #include <map> #include <cstdio> #include <cstdlib> #include <stack> #include <cstring> #include <map> #include <vector> #include <string> #include <queue> #include <cmath> #define eps 1e-7 #define mem(a , b) memset(a , b , sizeof(a) ) using namespace std ; const int MAXN = 1e5 + 5 ; const int INF = 0x7fffffff ; struct Edge { int adj ; int d ; int next ; } e[MAXN] ; int head[MAXN] ; int dis[MAXN] ; // 记录顶点 1 到其他 各顶点的最短距离 bool inq[MAXN] ; int cntq[MAXN] ; // 统计每个顶点的入队次数 int ecnt ; int N , L , D ; void chu() { mem(head , -1) ; ecnt = 0 ; } void init() // 输入和建图 { int i ; for(i = 0 ; i < L ; i ++) { int a , b , c ; scanf("%d%d%d" , &a , &b , &c) ; e[ecnt].adj = b ; e[ecnt].d = c ; e[ecnt].next = head[a] ; head[a] = ecnt ; ecnt ++ ; } for(i = 0 ; i < D ; i ++) { int a , b , c ; scanf("%d%d%d" , &a , &b , &c) ; e[ecnt].adj = a ; e[ecnt].d = -1 * c ; e[ecnt].next = head[b] ; head[b] = ecnt ; ecnt ++ ; } for(i = N ; i >= 2 ; i --) { int a , b , c = 0 ; a = i ; b = i - 1 ; e[ecnt].adj = b ; e[ecnt].d = c ; e[ecnt].next = head[a] ; head[a] = ecnt ; ecnt ++ ; } } queue<int> q ; int spfa(int u) { mem(inq , 0) ; mem(cntq , 0) ; while (!q.empty()) q.pop() ; q.push(u) ; inq[u] = true ; cntq[u] ++ ; while (!q.empty()) { int tmp = q.front() ; if(cntq[tmp] >= N) // 判断是否存在权值为负数的有向环 { return 0 ; } q.pop() ; inq[tmp] = false ; int i ; for(i = head[tmp] ; i != -1 ; i = e[i].next) { int v = e[i].adj ; int td = e[i].d ; if(dis[tmp] + td < dis[v]) { dis[v] = dis[tmp] + td ; if(!inq[v]) { q.push(v) ; inq[v] = true ; cntq[v] ++ ; } } } } return 1 ; } void solve() { int i ; for(i = 1 ; i <= N ; i ++) { dis[i] = INF ; } dis[1] = 0 ; int pan = spfa(1) ; if(!pan || dis[N] < 0) { puts("-1") ; } else if(dis[N] == INF) { puts("-2") ; } else { printf("%d\n" , dis[N]) ; } } int main() { while (scanf("%d%d%d" , &N , &L , &D) != EOF) { chu() ; init() ; solve() ; } return 0 ; }