| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 6832 | Accepted: 3292 |
Description
Input
Output
Sample Input
4 2 1 1 3 10 2 4 20 2 3 3
Sample Output
27
Hint
题意：输入N， ML， MD， N表示有N个牛按1-N排成一排，ML，表示有ML行，每行输入A, B, D表示A牛和B牛最远距离为D， MD表示有MD行，每行输入A,B,D表示A牛和B牛最近距离为D，求满足所有条件的1-N的最大距离。
思路：
从题目样例来看 N = 4， ML = 2， MD = 1；
牛1和牛3之间距离最大为10，牛2和牛4之间距离最大为20
牛2和牛3之间距离最短为3，设d[i]为牛i到牛1的距离，所以可以列出方程组：
d[3] - d[1] <= 10
d[4] - d[2] <= 20
d[3] - d[2] >= 3
还有隐含条件 d[i] <= d[i+1]
典型的差分约束。
可以把方程组写成如下形式：
d[3] - d[1] <= 10
d[4] - d[2] <= 20
d[2] - d[3] <= -3 则最后可以得出d[N] - d[1] <= x，建图用spfa求最短路即可。
（差分约束做最短路的时候得到的是最大值，做最长路的时候得到的是最小值）
需要注意的是如果求不出最短路，则输出-1，若1-N可以是无穷，则输出-2。那么要再加上一个判断负环操作。
1 #include <iostream> 2 #include <queue> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 #define maxn 1010 7 #define maxm 55000 8 #define INF 999999999 9 int head[maxn], dist[maxn], ans; 10 int N, ML, MD, a, b, c; 11 struct Edge{ 12 int u, v, w, next; 13 }edge[maxm]; 14 void addedge(int u, int v, int w){ 15 edge[ans].u = u; edge[ans].v = v; edge[ans].w = w; 16 edge[ans].next = head[u]; head[u] = ans++; 17 } 18 bool spfa(int start){ 19 int judge[maxn]; //判断负环 20 queue <int> q; 21 bool inq[maxn]; 22 for(int i = 0;i <= N; i++){ 23 judge[i] = 0; 24 dist[i] = INF; 25 } 26 memset(inq, 0, sizeof(inq)); 27 q.push(start); 28 inq[start] = 1; 29 dist[start] = 0; 30 while(!q.empty()){ 31 int x = q.front(); q.pop(); 32 for(int i = head[x]; i != -1; i = edge[i].next){ 33 if(dist[edge[i].v] > dist[x] + edge[i].w){ 34 dist[edge[i].v] = dist[x] + edge[i].w; 35 if(!inq[edge[i].v]){ //如果已经在队列中了，就不要重复加了 36 inq[edge[i].v] = 1; 37 q.push(edge[i].v); 38 judge[edge[i].v]++; 39 if(judge[edge[i].v] > N) return false; 40 } 41 } 42 } 43 inq[x] = 0; 44 } 45 return true; 46 } 47 int main(){ 48 while(scanf("%d%d%d",&N, &ML, &MD)!=EOF){ 49 ans = 0; //初始化边数为0 50 memset(head, -1, sizeof(head)); 51 while(ML--){ // d[b] - d[a] <= c 52 scanf("%d%d%d",&a,&b,&c); 53 addedge(a,b,c); 54 } 55 while(MD--){ //d[a] - d[b] <= -c 56 scanf("%d%d%d",&a,&b,&c); 57 addedge(b,a,-c); 58 } 59 for(int i = 2; i <= N; i++) addedge(i,i-1,0); //d[i-1] - d[i] <= 0 60 61 if(spfa(1)){ 62 if(dist[N] == INF) printf("-2\n"); 63 else printf("%d\n",dist[N]); 64 65 } 66 67 else printf("-1\n"); 68 } 69 70 return 0; 71 }
POJ 3169 Layout (差分约束+SPFA),布布扣,bubuko.com
原文：http://www.cnblogs.com/titicia/p/3879485.html