首页 > 代码库 > Layout---poj3169（差分约束+最短路spfa）
Layout---poj3169（差分约束+最短路spfa）
题目链接：http://poj.org/problem?id=3169
有n头牛站成一排 在他们之间有一些牛的关系比较好，所以彼此之间的距离不超过一定距离；也有一些关系不好的牛，希望彼此之间的距离大于等于一定距离；
关系好的有ml个（A B D）表示A牛和B牛之间的距离<=D 关系不好的有md个（A，B，D）表示A牛和B牛之间的距离>=D,求在满足条件的排列中，求出牛1和牛n的最大距离；
如果距离可以是无限大输出-2，如果不存在这样的排列输出-1；
我们用d[i]表示第i头牛的位置，因为牛是按照编号排列顺序的，
所以 d[i]-d[i-1]>=0； --------- d[i-1]-d[i]<=0;（i到i-1的距离是0）
关系好的 d[B]-d[A] <= C; --------- d[B]-d[A]<=C;（A到B的距离是C）
关系不好的 d[B]-d[a]>=C; ----------- d[A]-d[B]<=-C;（B到A的距离是-C）
我们要求是的d[n]-d[1]<=x中的x；
刚好满足差分约束系统，所以直接建图求1-n的最短路即可；如果存在负环则不存在这样的序列，用spfa判断负环，如果距离为无穷大说明可以是任意值，
#include <iostream>#include <stdio.h>#include <math.h>#include <string.h>#include <queue>#include <stack>#include <algorithm>#include <map>#include <string>typedef long long LL;#define INF 0x3f3f3f3f#define met(a, b) memset(a, b, sizeof(a))#define N 1500using namespace std;int n, md, ml, G[N][N], vis[N], dist[N], cnt[N];int spfa(int s){ for(int i=1; i<=n; i++) dist[i] = INF; met(vis, 0); met(cnt, 0); queue<int>Q; Q.push(s); vis[s] = 1; dist[s] = 0; cnt[s]++; while(!Q.empty()) { int p = Q.front();Q.pop(); vis[p] = 0; cnt[p] ++; for(int i=1; i<=n; i++) { if(dist[i]>dist[p]+G[p][i]) { dist[i] = dist[p]+G[p][i]; if(!vis[i]) { vis[i] = 1; cnt[i]++; if(cnt[i]>=n) return -1; Q.push(i); } } } } if(dist[n] == INF) return -2; return dist[n];}int main(){ while(scanf("%d %d %d", &n, &ml, &md) != EOF) { for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) G[i][j] = INF; G[i][i] = G[i][i-1] = 0; } int u, v, w; for(int i=1; i<=ml; i++) { scanf("%d %d %d", &u, &v, &w); G[u][v] = w; } for(int i=1; i<=md; i++) { scanf("%d %d %d", &u, &v, &w); G[v][u] = -w; } int ans = spfa(1); printf("%d\n", ans); } return 0;}
Layout---poj3169（差分约束+最短路spfa）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。