POJ 3169

發表於 更新於 分類於 Disqus： 文章字數： 975 所需閱讀時間 ≈ 3 分鐘
cow game, 差分约束

Layout

http://poj.org/problem?id=3169

数轴上放N个点(按照i的顺序坐标非严格单调递增

10000 个大于限制, 点i和点j距离不超过 di (1e6)

10000 个小于限制, 点i和点j距离不小于 di (1e6)

1s

64MB

求点1 和 点N的最大距离

题解

传说中日本众所周知的的cow game

也就是 全部小于号, (大于号同乘-1)

注意到上面要保证i的顺序( 所以 大-小 <= Di 或者 大减小 >= Di

然后说 差分约束本质上还是 最短路 只是需要建图

b-a <= d

转化成 a + d >= b, 所以 a -> b如果有边长d的话, 那么b的距离最小就是 a+d 还可能更小

b-a >= d的话

转化成 b-d >= a, 也就是 b -> a 如果有边长 (-d), 那么a的距离最小是 b-d, 还可能更小

总而言之转化成

点0 + ? >= 点1 的形式, 然后从点0 发一条长? 的边

代码

过不了编译版本

这poj g++版本太老了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (int i=a;i<n;i++)

ll read(){ll r;scanf("%lld",&r);return r;} // read
const int INF = 0x3f3f3f3f; // 1e9

vector<array<int,3> > e; // 有向边 [u,v,weight/length]

int main(){
  int N = read();
  int ML = read();
  int MD = read();

  // 建图
  rep(i,1,N) e.push_back({i+1, i, 0}); // 从i+1->i权值为0的边 保证顺序i的距离不大于i+1
  rep(i,0,ML){ //'喜欢'关系约束 <= DL
    int a = read();
    int b = read(); // 保证 b>a
    int d = read(); // |距离| <= DL[i]
    /* b-a<=d, 即 a+d>=b 从a到b权值为d的边 */
    e.push_back({a,b,d});
  }
  rep(i,0,MD){ //'不喜欢'关系约束 >= DD
    int a = read();
    int b = read(); // 保证 b>a
    int d = read(); // |距离| >= DD[i]
    /* BD - AD >= DD 即 BD - DD >= AD,  从BD到AD权值-DD的边*/
    e.push_back({b,a,-d});
  }

  // Bellman_Ford
  vector<int>dist(N+1,INF);// 最短距离
  dist[1] = 0;
  //循环N-1次 对所有边进行松弛操作
  rep(i,0,N-1) for(auto [u,v,w]: e) if(dist[u] != INF) dist[v] = min(dist[v], dist[u] + w);

  //再遍历一次所有边（第N次循环）如果本次有更新，则存在负环
  bool ngloop = false;
  for(auto [u,v,w]: e) if(dist[u] != INF && dist[u] + w < dist[v] ) ngloop = true;
  int ans = dist[N];
  if (ngloop) ans = -1;
  else if(ans == INF) ans = -2;
  printf("%d\n", ans);
  return 0;
}

AC 版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define mt make_tuple

ll read(){ll r;scanf("%lld",&r);return r;} // read
const int INF = 0x3f3f3f3f; // 1e9

// 没有tuple
struct edge{
  int u;
  int v;
  int w;
  // 结构体直接赋值也没有
  edge(int _u,int _v,int _w){
    u = _u;
    v = _v;
    w = _w;
  }
};

vector<edge> e; // 有向边 [u,v,weight/length]

int main(){
  int N = read();
  int ML = read();
  int MD = read();

  // 建图
  rep(i,1,N) e.push_back(edge(i+1, i, 0)); // 从i+1->i权值为0的边 保证顺序i的距离不大于i+1
  rep(i,0,ML){ //'喜欢'关系约束 <= DL
    int a = read();
    int b = read(); // 保证 b>a
    int d = read(); // |距离| <= DL[i]
    /* b-a<=d, 即 a+d>=b 从a到b权值为d的边 */
    e.push_back(edge(a,b,d));
  }
  rep(i,0,MD){ //'不喜欢'关系约束 >= DD
    int a = read();
    int b = read(); // 保证 b>a
    int d = read(); // |距离| >= DD[i]
    /* BD - AD >= DD 即 BD - DD >= AD,  从BD到AD权值-DD的边*/
    e.push_back(edge(b,a,-d));
  }

  // Bellman_Ford
  vector<int>dist(N+1,INF);// 最短距离
  dist[1] = 0;
  //循环N-1次 对所有边进行松弛操作
  rep(t,0,N-1) rep(i,0,e.size()){
    edge &uvw = e[i]; // 不支持auto
    int u = uvw.u;
    int v = uvw.v;
    int w = uvw.w;
    if(dist[u] != INF) dist[v] = min(dist[v], dist[u] + w);
  }

  //再遍历一次所有边（第N次循环）如果本次有更新，则存在负环
  bool ngloop = false;
  rep(i,0,e.size()){
    edge &uvw = e[i]; // 不支持auto
    int u = uvw.u;
    int v = uvw.v;
    int w = uvw.w;
    if(dist[u] != INF && dist[u] + w < dist[v] ) ngloop = true;
  }
  int ans = dist[N];
  if (ngloop) ans = -1;
  else if(ans == INF) ans = -2;
  printf("%d\n", ans);
  return 0;
}

总结

就是如何对差分变成图