首页 > 代码库 > poj 3169 Layout (差分约束)
poj 3169 Layout (差分约束)
题目连接：
http://poj.org/problem?id=3169
题目大意：
在一个农场里，等待喂养的牛都按照自己的编号从1—>n排列，但是牛之间有一些特殊的关系，比如牛i与牛j相互讨厌（关系1），那么这两只牛之间最少间隔x，牛i与牛j相互喜欢（关系2），那么这两只牛之间最多间隔x。一共有n头牛，ml个关系2，有md个关系1。问：在满足这约束条件后，1到n的最大距离为多少，如果存在负环输出-1，不存在最长距离输出-2，否则输出最长距离。
解题思路：
典型的差分约束问题，但是这个比较麻烦的是，有最大约束还有最小约束。（dist[i]表示的从1到i的最长距离）
喜欢的关系存在：（i<j）dist[j] - dist[i] <= x。等价于：dist[j] <= dist[i] + x。
讨厌的关系存在：（i<j）dist[j] - dist[i] >= x。等价于：dist[i] <= dist[j] + x。
经过推导，可以看出用spfa求最短路即可，这道题目的关键在于建图。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 #include <vector> 6 using namespace std; 7 8 #define INF 0x3f3f3f3f 9 #define maxn 101010 11 struct Edge12 {13 int e, w;14 Edge(int e=0, int w=0):e(e),w(w){}15 };16 17 vector<Edge> G[maxn];18 int dist[maxn];19 void init ();20 int spfa (int n);21 22 int main()23 {24 int n, ml, md;25 while (scanf ("%d %d %d", &n, &ml, &md) != EOF)26 {27 init ();28 int a, b, d;29 while (ml --)30 {31 scanf ("%d %d %d", &a, &b, &d);32 G[a].push_back(Edge(b, d));//对第二种关系正向建边33 }34 while (md --)35 {36 scanf ("%d %d %d", &a, &b, &d);37 G[b].push_back(Edge(a, -d));//对第一种关系反向建边38 }39 printf ("%d\n", spfa(n));40 }41 return 0;42 }43 void init ()44 {45 int i;46 for (i=0; i<maxn; i++)47 {48 G[i].clear();49 dist[i] = INF;50 }51 }52 int spfa (int n)53 {54 int vis[maxn], updata[maxn];55 queue<int>Q;56 memset (vis, 0, sizeof(vis));57 memset (updata, 0, sizeof(updata));58 Q.push (1);59 updata[1] = 1;60 dist[1] = 0;61 while (!Q.empty())62 {63 int p = Q.front();64 Q.pop();65 vis[p] = 0;66 int len = G[p].size();67 68 for (int i=0; i<len; i++)69 {70 Edge q = G[p][i];71 if (dist[q.e] > dist[p] + q.w)72 {73 dist[q.e] = dist[p] + q.w;74 updata[q.e] ++;75 Q.push (q.e);76 vis[q.e] = true;77 if (updata[q.e] == n)78 return -1;//有负环79 }80 }81 }82 if (dist[n] == INF)83 return -2;//无最长距离的路存在84 return dist[n];85 }
poj 3169 Layout (差分约束)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。