AcWing 1169. 糖果

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1169. 糖果原题链接中等

作者：

一只野生彩色铅笔 , 2021-02-25 17:27:01 , 所有人可见 , 阅读 3065

47

17

差分约束

一、求不等式组的可行解

！！！源点需要满足的条件：从源点出发，一定可以走到所有的边。！！！

步骤：
1. 先将每个不等式 $x_i \le x_j + c_k$，转化成一条从 $x_j$ 走到 $x_i$，长度为 $c_k$ 的边。
2. 找到一个超级源点，使得该源点一定可以遍历到所有边
3. 从源点求一遍单源最短路

结果1：如果存在负环，则原不等式组一定无解
结果2：如果没有负环，则 $dist[i]$ 就是原不等式组的一个可行解

二、如何求最大值或者最小值，这里的最值指的是每个变量的最值

结论：如果求的是最小值，则应该求最长路；如果求的是最大值，则应该求最短路。

问题：如何转化 $x_i \le c$，其中 $c$ 是一个常数，这类的不等式。

方法：建立一个超级源点0，然后建立 0 -> i 的边，长度是 $c$ 即可。

以求 $x_i$ 的最大值为例：

求所有从 $x_i$ 出发，构成的多个形如如下的不等式链
$$ x_i \le x_j +c_1 \le x_k + c_2 + c_1 \le ··· \le x_0 + c_1 + c_2 + ··· + c_m \qquad(x_0 = 0) $$
所计算出的上界，最终 $x_i$ 的最大值等于所有上界的最小值。
这里所有上界的最小值可以理解这么一个例子： QQ截图20210225172450.png

把上述转换成图论的问题，就是求 $dist[i]$ 的最小值，即最短路求解

求 $x_i$ 的最小值 时则完全相反，求一个形如如下不等式链所计算出的下界，最终在所有下界里取最大值
$$ x_i \ge x_j +c_1 \ge x_k + c_2 + c_1 \ge ··· \ge x_0 + c_1 + c_2 + ··· + c_m \qquad(x_0 = 0) $$
转换成图论的问题，就是求 $dist[i]$ 的最大值，即最长路求解

AcWing 1169. 糖果

代码：

#include <iostream>
#include <cstring>

typedef long long LL;
const int N = 1e5 + 10, M = 3 * N;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N], cnt[N], q[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() {
    //因为是求所有x_i的最小值，因此就是求不等式的下界的最大值
    //转而就是求图论的最长路
    int hh = 0, tt = 1;
    memset(dist, -0x3f, sizeof dist);
    dist[0] = 0;
    q[0] = 0;

    //建立一个能够到所有点的虚拟源点0
    for (int i = 1; i <= n; ++i) add(0, i, 1);  //x_0 <= x_i + 1

    //这题在判负环的时候会TLE
    //上一次的“负环”题目中的trick方法还是太玄学了
    //这里用一个不会TLE的判负环方法，那就是把SPFA算法中的循环队列改为栈
    //这样对于遇到的负环，就不会加入队尾，知道再次遍历完整个队列才去算他
    //遇到负环会直接在栈顶连续入栈出栈，直到判断他的cnt[i] >= n+1，即发现负环
    while (hh != tt) {
        int t = q[--tt];
        st[t] = false;

        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 + 1) return true;

                if (!st[j]) {
                    st[j] = true;
                    q[tt++] = j;
                }
            }
        }
    }
    return false;
}
int main() {
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    while (m--) {
        int x, a, b;
        scanf("%d%d%d", &x, &a, &b);
        if (x == 1) add(a, b, 0), add(b, a, 0);
        else if (x == 2) add(a, b, 1);
        else if (x == 3) add(b, a, 0);
        else if (x == 4) add(b, a, 1);
        else if (x == 5) add(a, b, 0);
    }
    if (spfa()) puts("-1");
    else {
        LL res = 0;
        for (int i = 1; i <= n; ++i) res += dist[i];
        printf("%lld\n", res);
    }
    return 0;
}

12 评论

jatro13 2023-02-23 21:17

神奇。。。竟然没用using namespace std

wellerency 2022-05-18 12:26

求解，我这个代码如果用超级源点不会tle，全部入栈就会超时

wellerency 2022-05-18 12:27

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+100,M=3e5+100;
int n,k;
typedef long long ll;
struct node
{
    int ne,to,w;
}e[M];
int idx,h[N];
void add(int x,int y,int w)
{
    idx++;
    e[idx].ne=h[x];e[idx].to=y;e[idx].w=w;h[x]=idx;
}

int dist[N],cnt[N];
bool st[N];
bool spfa()
{
    //deque<int>q;
    stack<int>q;
    memset(dist,-0x3f,sizeof dist);

    for(int i=1;i<=n;i++)
    {
        q.push(i);
        dist[i]=1;st[i]=1;
    }

    while(q.size())
    {
        int x=q.top();q.pop();
        st[x]=0;
        //cout<<"dist"<<dist[x]<<endl;
        for(int i=h[x];i;i=e[i].ne)
        {
            int y=e[i].to,w=e[i].w;
            if(dist[y]<dist[x]+w)
            {
                dist[y]=dist[x]+w;
                cnt[y]=cnt[x]+1;
                if(cnt[y]>=n)return 1;  //存在负环 
                if(!st[y])
                {
                    q.push(y);
                    st[y]=1;
                }
            }
        }
    }

    return 0;   //不存在负环 
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)
    {
        int x,a,b;
        scanf("%d%d%d",&x,&a,&b);
        if(x==1)add(a,b,0),add(b,a,0);
        else if(x==2)add(a,b,1);
        else if(x==3)add(b,a,0);
        else if(x==4)add(b,a,1);
        else if(x==5)add(a,b,0);
    }

    //for(int i=1;i<=n;i++)add(0,i,1);

    if(spfa())puts("-1");
    else 
    {
        ll res=0;
        for(int i=1;i<=n;i++)
            res+=dist[i];
        printf("%lld\n",res);
    }

    return 0;
}

xiuzhiyuan 2022-10-23 10:52 回复了 wellerency 的评论

好玄学，我用全部入栈也超时了！！

糖豆 2022-11-14 15:02 回复了 xiuzhiyuan 的评论

我的可以AC啊，但我用的是队列

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010, M = 300010;
int n, m;

int q[N], cnt[N];
LL dist[N];
bool st[N];

int h[N], e[M], w[M], ne[M], idx;
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool spfa() {
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i++) {
        dist[i] = 1;
        st[i] = true;
        q[++tt] = i;
    }

    while (hh <= tt) {
        int u = q[hh++];
        st[u] = false;

        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] < dist[u] + w[i]) {
                dist[j] = dist[u] + w[i];
                cnt[j] = cnt[u] + 1;
                if (cnt[j] >= n) return true;
                if (!st[j]) {
                    q[++tt] = j;
                    st[j] = true;
                }
            }
        }
    }
    return false;
}
int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while (m--) {
        int x, a, b;
        cin >> x >> a >> b;
        if (x == 1) add(a, b, 0), add(b, a, 0); // A=B,A>=B,B>=A
        if (x == 2) add(a, b, 1);               // A<B,B-1>=A
        if (x == 3) add(b, a, 0);               // A>=B,B->A
        if (x == 4) add(b, a, 1);               // A>B,A>=B+1,B->A
        if (x == 5) add(a, b, 0);               // A<=B,B>=A,A->B
    }

    if (spfa())
        puts("-1");
    else {
        LL res = 0;
        for (int i = 1; i <= n; i++) res += dist[i];
        printf("%lld\n", res);
    }
    return 0;
}