最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

热点在线丨AcWing1170. 排队布局[USACO05]

来源：博客园


【资料图】

解题思路

\(\qquad\)这题也是一个比较裸的差分约束：多了的那个输出\(-2\)的其实就是在差分约束系统中\(1\)号点和\(n\)号点没有约束关系，也就是\(1\)和\(n\)号不连通。由于这里要求最大距离，所以我们在系统中应该跑最短路

从题目中我们可以看出这样几条约束关系：\(\qquad\quad\) \(\large x_{i+1}\ge x_i\Rightarrow x_i\le x_{i+1}+0\) ：因为后面的牛的位置一定不能比前面的靠前。

\(\qquad\quad\)在\(M_L\)条的关系中 \(\large x_b-x_a\le L\Rightarrow x_b\le x_a+L\)：距离不大于\(L\)

\(\qquad\quad\)在\(M_D\)条的关系中 \(\large x_b - x_a\ge D\Rightarrow x_a-x_b\le -D\Rightarrow x_a\le x_b-D\)：距离不小于\(D\)

然后又没有一个源点可以遍历所有边，所以我们还是建立超级源点\(0\)让它和所有点连边权\(0\)的边。整理关系得到\(\Large\left \{\begin{array}cx_i\le x_{i+1}+0,\\x_b\le x_a+L,\\ x_a\le x_b-D,\\x_i\le x_0+0.\end{array}\right.\)

代码

#include #include #include using namespace std;const int N = 1010, M = 21010, INF = 0x3f3f3f3f;int h[N], e[M], w[M], ne[M], idx;int dist[N], cnt[N], q[N], st[N];int hh, tt(1), md, ml, n, ring;void add(int a, int b, int c) {    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;}void spfa(int S) {    memset(dist, 0x3f, sizeof dist);    memset(st, 0, sizeof st);    memset(cnt, 0, sizeof cnt);        q[tt ++ ] = S, st[S] = 1, dist[S] = 0;        while (hh != tt)     {        int t = q[hh ++ ];        if (hh == N) hh = 0;        st[t] = 0;                for (int i = h[t]; ~i; i = ne[i])         {            int j = e[i];            if (dist[j] > dist[t] + w[i])             {                dist[j] = dist[t] + w[i];                cnt[j] = cnt[t] + 1;                if (cnt[j] >= n) return void (ring = true);                if (!st[j])                 {                    st[j] = true ;                    q[tt ++ ] = j;                    if (tt == N) tt = 0;                }            }        }    }        return void (ring = false);}int main() {    scanf("%d%d%d", &n, &ml, &md);        memset(h, -1, sizeof h);    while (ml -- )     {        int a, b, l;        scanf("%d%d%d", &a, &b, &l);        if (a > b) swap(a, b);        add(a, b, l);    }        while (md -- )    {        int a, b, d;        scanf("%d%d%d", &a, &b, &d);        if (a > b) swap(a, b);        add(b, a, -d);    }        for (int i = 1; i < n; i ++ )         add(i + 1, i, 0), add(0, i, 0);    add(0, n, 0);        spfa(0);    if (ring) puts("-1");    else {        spfa(1);        printf("%d\n", dist[n] == INF ? -2 : dist[n]);    }        return 0;}

关键词： 约束系统 可以看出 最大距离