P1993 小K的农场 && 差分约束

时间：2024-01-13 21:28:56

首先第一篇讨论的是差分约束系统解的存在

差分约束系统是有 \(n\) 个变量及 \(m\) 个（如 \(x_{i} - x_{j} \leq a_{k}\) ）关系组成的系统

差分约束解的求解可以转化为图中最短路的求解问题

对一个标准的差分约束式， 我们可以如下连边$$x_{i} - x_{j} \leq a_{k}\ \Rightarrow \ V(j\ ,\ i), w[j,i] = a[k]$$

对于一个不是那么标准的差分约数式， 我们可以做如下变形：$$x_{i} - x_{j} \geq a_{k} \Rightarrow x_{j} - x_{i} \leq -a_{k}$$$$x_{i} - x_{j} < a_{k} \Rightarrow x_{i} - x_{j} \leq a_{k} + 1$$$$x_{i} = x_{j} \Rightarrow x_{i} - x_{j} \leq 0 \ & &\ x_{j} - x_{i} \leq 0$$

然后连边， 转化为最短路是否有解的问题， 考虑 \(SPFA\) 解决， 值得注意的是， 这个图不一定只有一个联通块， 所以我们从源点 \(0\) 出发， 初始先像每一个点连边， 权为 \(0\) ， 以源点为起点进行 \(SPFA\) 便会比较方便了

P.s : 一般差分约数只是判断是否有解的数据会比较恶心，所以可以使用 \(SPFA(dfs)\) 来代替 \(SPFA(bfs)\) ， 遇到负环直接退出， 效率较高

可以试想一下， 跑出来的最短路是什么呢？ 无法到达又说明着什么呢？ 这将会在下一篇进行探讨

P1993 小K的农场

题目描述

小K在MC里面建立很多很多的农场，总共n个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共m个），以下列三种形式描述：

农场a比农场b至少多种植了c个单位的作物，

农场a比农场b至多多种植了c个单位的作物，

农场a与农场b种植的作物数一样多。

但是，由于小K的记忆有些偏差，所以他想要知道存不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。

输入输出格式

输入格式：

第一行包括两个整数 n 和 m，分别表示农场数目和小 K 记忆中的信息数目。

接下来 m 行：

如果每行的第一个数是 1，接下来有 3 个整数 a,b,c，表示农场 a 比农场 b 至少多种植了 c 个单位的作物。

如果每行的第一个数是 2，接下来有 3 个整数 a,b,c，表示农场 a 比农场 b 至多多种植了 c 个单位的作物。如果每行的第一个数是 3，接下来有 2 个整数 a,b，表示农场 a 种植的的数量和 b 一样多。

输出格式：

如果存在某种情况与小 K 的记忆吻合，输出“Yes”，否则输出“No”。

板题， 手算， 转换一下关系连边即可。

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

using namespace std;

int RD(){

    int flag = 1, out = 0;char c = getchar();

    while(c < '0' || c > '9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

const int maxn = 1000019, INF = 1e9 + 19;

int head[maxn], nume = 1;

int num, ni;

struct Node{

    int u, v, dis, nxt;

    }E[maxn << 3];

void add(int u, int v, int dis){

    E[++nume].nxt = head[u];

    E[nume].v = v;

    E[nume].dis = dis;

    head[u] = nume;

    }

int d[maxn];

bool ins[maxn], flag;

void SPFA(int u){

    ins[u] = 1;

    for(int i = head[u];i;i = E[i].nxt){

        int v = E[i].v, dis = E[i].dis;

        if(d[u] + dis < d[v]){

            if(ins[v]){flag = 1;return ;}

            d[v] = d[u] + dis;

            SPFA(v);

            }

        }

    ins[u] = 0;

    }

int main(){

    num = RD();ni = RD();

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

    for(int i = 1;i <= ni;i++){

        int cmd = RD(), a = RD(), b = RD(), c;

        if(cmd == 1)c = RD(), add(a, b, -c);

        else if(cmd == 2)c = RD(), add(b, a, c);

        else add(a, b, 0), add(b, a, 0);

        }

    for(int i = 1;i <= num;i++)d[i] = INF;

    SPFA(0);

    flag ? puts("No") : puts("Yes");

    return 0;

    }

相关文章