Acwing 1170. 布局（差分约束）

2022-11-28 74

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 笔记

Acwing 1170. 布局

题意

当排队等候喂食时，奶牛喜欢和它们的朋友站得靠近些。

农夫约翰有 N 头奶牛，编号从 1 到 N，沿一条直线站着等候喂食。

奶牛排在队伍中的顺序和它们的编号是相同的。

因为奶牛相当苗条，所以可能有两头或者更多奶牛站在同一位置上。

如果我们想象奶牛是站在一条数轴上的话，允许有两头或更多奶牛拥有相同的横坐标。

一些奶牛相互间存有好感，它们希望两者之间的距离不超过一个给定的数L。

另一方面，一些奶牛相互间非常反感，它们希望两者间的距离不小于一个给定的数 D

给出 M L条关于两头奶牛间有好感的描述，再给出 M D 条关于两头奶牛间存有反感的描述。

你的工作是：如果不存在满足要求的方案，输出 −1；如果 1 号奶牛和 N 号奶牛间的距离可以任意大，输出 −2；否则，计算出在满足所有要求的情况下，1 号奶牛和N 号奶牛间可能的最大距离。

思路

设一组变量 x i 表示第 i 只奶牛所在的位置，因为题目要求奶牛按照编号的顺序站，所以会有以下不等式约束条件：

① x i ≤ x i + 1 同时，根据M L 和 M D 的约束，会有以下不等式约束条件

② x b − x a ≤ L 其中 x a ≤ x b

③ x b − x a ≥ D 其中 x a ≤ x b

因为奶牛之间只有相对关系，没有绝对关系，也即某一个奶牛在数轴上的具体位置不重要，只需要满足不等式的约束条件即可。因为题目要求最大距离，所以应该用差分约束的最短路模型。

因为题目不需要求出每个奶牛具体的位置，所以无需添加绝对关系不等式。

首先考虑问题1，不满足要求即图中存在负环。

问题2、3：1 号奶牛和 N 号奶牛之间的距离可以任意大等价于，从 1 到 N 的最短路可以无限大，所以从1 求一遍最短路判断 d[n] 是否等于 INF 即可，如果 == INF 说明距离可以任意大，否则d[n]即为求出最大的距离。

考虑这样一个问题：为什么判断是否满足条件时需要将所有点 push 进队列，而求最大距离时，只需要将节点 1 push 进队列？

是否满足条件 == 图中是否存在负环如果只把 1 push 进队列，1 可能到达不了所有的点，所以要把所有点 push进去

1 到 N 的最大距离，经典的最短路问题，所以只需要把起点 push 进队列，无需考虑是否能到达所有的点。

代码

// Author：zzqwtcc
// Problem: 排队布局
// Contest: AcWing
// Time：2021-10-29 19:16:45
// URL: https://www.acwing.com/problem/content/1172/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
#include<bits/stdc++.h>
#include<unordered_map>
// #define int long long
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define MOD 998244353
#define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i))
#define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i))
// #define debug(x,y) cerr << (x) << " == " << (y) << endl;
#define endl '\n'
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T> inline T lowbit(T x) { return x & -x; }
template<typename S,typename T>void debug(S s, T t){cerr << s << " == " << t << endl;}
template<typename T>void debug(T t){cerr << t << endl;}
template<typename T>void debug(T t[],int st,int ed){for(int i = st; i <=ed;++i){cerr << t[i] << " ";}cerr << endl;}
template<typename T>void debug(const vector<T>&t){for(int i =0 ; i < t.size();++i)cerr << t[i] << " ";cerr << endl;}
// template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; }
const int N = 1010,M = 2e4 + N + 10;
int n;
int m1,m2;
int h[N],e[M],ne[M],w[M],idx;
int cnt[N],d[N];
bool st[N];
void add(int a,int b,int c){
  e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
bool spfa(int size){
  memset(d,0x3f,sizeof d);
  memset(cnt,0,sizeof cnt);
  memset(st,0,sizeof st);
  queue<int>q;
  for(int i = 1; i <= size;++i){
    q.push(i);
    d[i] = 0;
  }
  while(q.size()){
    int u = q.front();
    q.pop();
    st[u] = false;
    for(int i = h[u];~i;i = ne[i]){
      int j = e[i];
      int dis = w[i];
      if(d[j] > d[u] + dis){
        d[j] = d[u] + dis;
        cnt[j] = cnt[u] + 1;
        if(cnt[j] >= n)return false;
        if(!st[j]){
          st[j] = true;
          q.push(j);
        }
      }
    }
  }
  return true;
}
void solve() {
    cin >> n >> m1 >> m2;
    memset(h,-1,sizeof h);
    while(m1--){
      int a,b,c;scanf("%d%d%d",&a,&b,&c);
      if(a > b)swap(a,b);
      add(a,b,c);
    }
    while(m2--){
      int a,b,c;scanf("%d%d%d",&a,&b,&c);
      if(a > b)swap(a,b);
      add(b,a,-c);
    }
    for(int i = 1; i <= n - 1;++i){
      add(i + 1,i,0);
    }
    if(!spfa(n))puts("-1");
    else {
      spfa(1);
      if(d[n] == INF)puts("-2");
      else printf("%d\n",d[n]);
    }
}
signed main() {
    //int _; cin >> _;
    //while (_--)
        solve();
    return 0;
}

Acwing 1170. 布局（差分约束）

Acwing 1170. 布局

题意

代码

热门文章

最新文章

相关电子书

Acwing 1170. 布局 （差分约束）

Acwing 1170. 布局

题意

代码

热门文章

最新文章

相关电子书

Acwing 1170. 布局（差分约束）