差分约束

  • 差分约束

    1、差分约束：有 $T$ 组样例($T \leq 10^3$)，对于每组样例，给定 $n$ 和 $m$ ($n,m \leq 5 \times 10^3$)，表示有 $n$ 个未知量和一个大小为 $m$ 的不等式组。对于 $m$ 个不等式，输入 $1\ i\ j\ z$ 表示 $x_i \leq x_j + z$，输入 $2\ i\ j\ z$ 表示 $x_i \geq x_j + z$，输入 $3\ i\ j$ 表示 $x_i = x_j$。需要判断不等式组是否存在一组未知量可以作为解，存在输出 $YES$ 否则输出 $NO$
    2、差分约束系统是一种特殊的，形如 $x_i - x_j \leq c_k$ 的 $n$ 元一次不等式组，其每一个约束条件都可以变形为 $x_i \leq x_j + c_k$。观察变形后的约束条件，很接近先前单源最短路的松弛操作后保证的状态 $d[y] \leq d[x] + w$ (三角形不等式)，不妨把每个解 $x_i$ 看作图中一个点，对应地从节点 $j$ 向 $i$ 连一条长度为 $z$ 的边(将约束条件转换成图)，如果在这样的图上跑完了最短路，则一定保证约束条件满足。即，求 $x_i$ 的一组解等价于在图上求一组最短距离 $d[]$ (即 $x_i = d[i]$)，如果这样的图存在，即 $d[]$ 存在且合法(没有负环)，说明存在至少一组解
    3、实现时，最短路需要一个起点，但因为无法保证整个图连通，则以任意点作为起点都不能保证得到到所有点的最短路，所以需要构建一个虚拟源点 $0$ 作为起点且到所有点距离为 $0$，将整个图连通。对于题面给出的第一种不等式，是与约束条件相同的形式；对于第二种不等式应将 $\geq$ 式转换成 $\leq$ 式，即 $x_j \leq x_i - z$，边权为 $-z$；对于第三种等式，可以相似地转换成 $x_i \leq x_j + 0$ 且 $x_j \leq x_i + 0$，即 $x_i, x_j$ 点双向连通且边权为 $0$。此处的连边规则在下面的补充处另有详细说明，并非一定移项成这种形式
    4、对于最短路的实现，由于存在负权边且需要判断负环，所以用 Bellman-Ford 或 SPFA，注意由于多加了一个虚拟源点，因此 SPFA 判断是否负环的条件要修改为 ++cnt[y] > n 或 ++cnt[y] >= n + 1(Bellman-Ford 也同理需要多松弛一次)
    5、运行后，$d[]$ 的值就是 $x$ 的一组解。容易发现，这组解同时增减相同的值 $a$ 后也仍是一组解，因为有 $(x_i + a) - (x_j + a) = x_i - x_j \leq c_k$，增减的值在约束条件中会被抵消

  • 补充：求差分约束的确定最值

    1、接上文，最终求到的解可以同时增减且仍然成立，所以实际得到的答案中确定的部分是 $x_1, x_2, x_3, \ldots$ 的取值范围之间的相对大小关系，某些题目会补充一个条件，通过给定一个解的基准点的最值(最大值或最小值)，便可以确定基准点的绝对的取值范围，从而确定出其他点的绝对的取值范围，并问其他点的取值最值(此时便可以确定下来了)。但注意前提，图自身一定要连通(不算额外添加的虚拟源点)
    2、如上例(注意，上例并不满足图自身连通的前提条件！在此假设条件成立，仅作示例说明思路)：若补充条件假设 $x_1$ 的最大值为 $0$，则 $x_1$ 便是解的基准点，且 $x_1$ 的取值范围也已确定(最大为 $0$，最小值也会因最大值确定而确定)，其他点的取值范围借由与 $x_1$ 的相对大小关系也可以确定，题目改问有解时输出 $x_1 \sim x_n$ 的最大值
    3、此时，需要额外思考：如果题目要求 $x_i$ 的最大值(即该例的情况)，需要的是最短路，因为执行最短路后会满足 $x_j \leq x_i + w$ 的恒成立条件，那么此时对于每个 $x_j$ 都是最大值(因为如果 $x_j$ 不是最大值，一定还有 $x_i + w \lt x_j$ 可以松弛它)。类似地，如果题目要求 $x_i$ 的最小值(下一道例题的情况)，需要的是最长路，因为执行最长路后会满足 $x_j \geq x_i + w$ 的恒成立条件，那么此时对于每个 $x_j$ 都是最小值。注意，最大最小值与最短最长路的算法本身没有关系，只是运用其思路，利用运行后满足的恒成立条件来确定最值(实现时只需在最短路上稍作更改)
    4、具体实现时，需要先确定求哪种最值，确定恒成立关系(可以记住上述推理的结论，最大值最短路、最小值最长路)，再将给定的约束条件移项成对应路的恒成立条件的形式(求不同的最值连边构造的图是不一样的)，以确定连边方向是 $i \to j$ 还是 $j \to i$。因此，对于上例的最短路，应转换成 $a \leq b + w$ 的形式连 $b \to a = w$ 的边；而对于最长路，是转换成 $a \geq b + w$ 的形式连 $b \to a = w$ 的边
    5、回到该例，由上面分析可知，连边规则与最短路的部分与下面代码示例相同，最后得到 $d[]$ 数组为一组可行解(且因为是最短路求得，每个解都是各自范围的最大值)。不过注意，此时还不能直接输出，因为基准的 $d[1]$ 应该为 $0$，而实际所求并不一定，那么实际与基准偏差的值即为 $d[1] - 0 = d[1]$，输出时每个点应减去偏差，即应该输出 $d[i] - d[1]$，即为答案(再次说明，该例实际不满足图连通的条件，因此更改代码后答案会错，仅作示例说明思路)

  • 代码实现

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

using ll = long long;
const int N = 1e4 + 10;
const ll INF = 2e18;

struct Edge
{
        ll x, w;
};
vector<Edge> g[N];

int n, m;
ll d[N];

// SPFA，返回是否有负环
bool SPFA(int st)
{
    for(int i = 1; i <= n; i++)
        d[i] = INF;
    d[st] = 0;

    queue<int> q;
    bitset<N> inq;
    int cnt[N] = {};

    q.push(st), inq[st] = true;
    while (q.size())
    {
        int x = q.front();
        q.pop(), inq[x] = false;

        for (auto &[y, w] : g[x])
        {
            if (d[x] + w < d[y])
            {
                if (++cnt[y] > n)
                    return true;

                d[y] = d[x] + w;
                if (!inq[y])
                    q.push(y), inq[y] = true;
            }
        }
    }
    return false;
}

void solve()
{
    cin >> n >> m;

    // 清空图
    for (int i = 1; i <= n; i++)
        g[i].clear();

    // 建图
    while (m--)
    {
        int op;
        cin >> op;

        int i, j, z;
        if (op == 1)
        {
            // x_i <= x_j + z，连 j ->  i 边权为 z
            cin >> i >> j >> z;
            g[j].push_back({i, z});
        }
        else if (op == 2)
        {
            // x_j <= x_i - z，连 i -> j 边权为 -z
            cin >> i >> j >> z;
            g[i].push_back({j, -z});
        }
        else
        {
            // x_i = x_j，双向连通 i--j 边权为 0
            cin >> i >> j;
            g[i].push_back({j, 0});
            g[j].push_back({i, 0});
        }
    }

    // 建立虚拟源点
    for (int i = 1; i <= n; i++)
        g[0].push_back({i, 0});

    // 判断负环(是否有一组解)
    if (SPFA(0))
        cout << "NO" << '\n';
    else
        cout << "YES" << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

例-Intervals

  • Intervals

    1、Intervals(改编自 POJ 1201)：请构造一个集合，给定 $n$ 个条件($n \leq 5 \times 10^4$)，对于每个条件，输入 $a_i, b_i, c_i$，表示要求集合中元素值在 $[a_i, b_i]$ 之间的数字至少出现 $c_i$ 次，即从 $[1, 5 \times 10^4]$ 尽可能少地选择数字满足条件，求这个集合的最小大小
    2、差分约束实际的题目中常会有很多隐含的条件，可能需要全部找到才能满足题目所给的模型，甚至差分约束条件也会被包装隐藏，较常用的一种获得差分约束条件的思想是前缀和。如该例，设 $d[i]$ 存储 $1 \to i$ 选择了多少个元素(实际也是一个前缀和)，那么对于给出的一个条件 $a, b, c$，可以翻译为 $d[b] - d[a-1] \geq c$ (即$[a, b]$ 间选择的元素至少为 $c$ 个)，这便将条件翻译为了差分约束条件，题目实际便是求这些不等式组的一组解中 $d[5\times 10^4]$ 的最小值
    3、由于要求最小值，所以应该要跑最长路，则上式应该变为最长路的恒成立条件的形式 $d[b] \geq d[a-1] + c$，应建立 $a-1$ 到 $b$ 的边权为 $c$ 的边。但只靠这样建图，不能满足求差分约束确定最值所需的图自身联通的前提条件，所以需要找其他隐含条件：因为是前缀和，所以有 $d[i] \geq d[i-1] + 0$，可以建立 $i-1$ 到 $i$ 的边权为 $0$ 的边，前缀和还有 $d[i-1] \geq d[i] - 1$，可以建立 $i$ 到 $i-1$ 的边权为 $-1$ 的边，这样便满足了图自身连通的条件(此外，常见的条件还有 $d[i] \leq d[0] = 0$ 连通 $0 \to i = 0$ 的边，此处的 $0$ 点并非添加的虚拟源点，而是前缀和本身自带的)。此外，隐含的基准值是 $d[0]$ 最小值为 $0$，因此偏差为 $d[0] - 0 = 0$ (实际的 $d[0] = 0$ 减去基准值 $0$)，所以最终输出的答案为 $d[m] - d[0] = d[m]$
    4、实现时要注意，求最长路在最短路基础上修改：$d[]$ 初始化为 $-\infty$，松弛条件变为 $d[x] + w > d[y]$，由于是求最长路，所以原先判断负环应改为判断正环防止无限累加(判断的方式相同)，可以证明，该题目不存在正环(建图左连向右边权总是非负，唯一的 $i$ 连向 $i-1$ 的情况边权为 $-1$，而前缀和元素与前一个元素差值最大为 $1$，因此成环也绝不为正环)

  • 代码实现

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

using ll = long long;
const int N = 5e4 + 10;
const ll INF = 2e18;

struct Edge
{
        ll x, w;
};
vector<Edge> g[N];

// m 为可能所选最大的元素的范围，+1 预留出一个下标 0
int n, m = 5e4 + 1;
ll d[N];

// 最长路，图连通，且可以证明该题没有正环，不需要判断正环
void SPFA(int st)
{
    // 最长路，初始化为 -INF
    for (int i = 1; i <= m; i++)
        d[i] = -INF;
    d[st] = 0;

    queue<int> q;
    bitset<N> inq;

    q.push(st), inq[st] = true;
    while (q.size())
    {
        int x = q.front();
        q.pop(), inq[x] = false;

        for (auto &[y, w] : g[x])
        {
            // 最长路，d[x] + w > d[y] 才松弛
            if (d[x] + w > d[y])
            {
                d[y] = d[x] + w;
                if (!inq[y])
                    q.push(y), inq[y] = true;
            }
        }
    }
}

void solve()
{
    cin >> n;
    // 差分约束条件建图，d[b] >= d[a-1] + c
    for (int i = 1; i <= n; i++)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        g[a - 1].push_back({b, c});
    }

    // 隐含条件建图
    for (int i = 1; i <= m; i++)
    {
        // 隐含条件 d[i] >= d[i-1] + 0
        g[i - 1].push_back({i, 0});
        // 隐含条件 d[i-1] >= d[i] - 1
        g[i].push_back({i - 1, -1});
    }

    SPFA(0);

    // 输出即 d[m] - 偏差 0 = d[m]
    cout << d[m] << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

例-奇怪的奶牛

  • 奇怪的奶牛

    1、奇怪的奶牛(改编自 POJ 3169)：有 $n$ 头奶牛按编号从小到大排列($n \leq 10^3$)，它们中有 $t$ 对好朋友和 $r$ 对坏朋友($t,r \leq 10^4$)。对于好朋友，输入 $x, y, w$ 表示 $x, y$ 的距离不超过 $w$(即中间间隔至多 $w-1$ 个位置)；对于坏朋友，输入 $x, y, w$ 表示 $x, y$ 的距离不少于 $w$。一个位置可以放多头奶牛，如果希望农场越长越好，输出最长的长度，如果无限长输出 $-2$，如果不存在方案输出 -1
    2、令 $d[i]$ 表示第 $i$ 头奶牛的位置，则好朋友的约束条件可以翻译为 $d[y] - d[x] \leq w$，坏朋友的约束条件可以翻译为 $d[y] - d[x] \geq w$，最终要求 $d[n]$ 的最大值
    3、由于是最大值，所以用最短路。对于好朋友，变换约束条件为 $d[y] \leq d[x] + w$，连 $x \to y = w$ 的边；对于坏朋友，变换约束条件为 $d[x] \leq d[y] - w$，连 $y \to x = -w$ 的边。跑 SPFA，如果有负环说明没有方案；如果 $d[n]$ 没有约束没被联通(没有被更新)说明可以无限长；此外基准点为 $d[1]$ 的最大值为 $1$，偏差为 $0$，因此答案为 $d[n] - 0 = d[n]$

  • 代码实现

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

using ll = long long;
const int N = 1e3 + 10;
const ll INF = 2e18;

struct Edge
{
        ll x, w;
};
vector<Edge> g[N];

int n, t, r;
ll d[N];

// 返回 d[n] 最大位置，返回 -1 表示负环，返回 -2 表示 d[n] 没有约束无穷大
ll SPFA(int st)
{
    for (int i = 1; i <= n; i++)
        d[i] = INF;
    d[st] = 1; // 1 号牛放在 1 号位置

    queue<int> q;
    bitset<N> inq;
    int cnt[N] = {};

    q.push(st), inq[st] = true;
    while (q.size())
    {
        int x = q.front();
        q.pop(), inq[x] = false;

        for (auto &[y, w] : g[x])
        {
            // 最短路
            if (d[x] + w < d[y])
            {
                if (++cnt[y] >= n)
                    return -1;

                d[y] = d[x] + w;
                if (!inq[y])
                    q.push(y), inq[y] = true;
            }
        }
    }

    // d[n] 没有约束不会被更新，INF
    return d[n] == INF ? -2 : d[n];
}

void solve()
{
    cin >> n >> t >> r;

    // 好朋友，d[y] <= d[x] + w
    for (int i = 1; i <= t; i++)
    {
        ll x, y, w;
        cin >> x >> y >> w;
        g[x].push_back({y, w});
    }

    // 坏朋友，d[x] <= d[y] - w
    for (int i = 1; i <= r; i++)
    {
        ll x, y, w;
        cin >> x >> y >> w;
        g[y].push_back({x, -w});
    }

    cout << SPFA(1);
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

二分图染色

  • 二分图染色

    1、二分图判定：给定一个 $n$ 点 $m$ 边的图，对于每条边输入 $x, y$ 表示 $x, y$ 之间存在一条无向边，判断它是否是一个二分图，输出 $YES$ 或 $NO$
    2、二分图：在一个无向图上，如果不存在奇数长度的环，则就是一个二分图。在判断时，可以通过染色的方式，共有两种颜色(例如黑和白)，一个点的出点要染上与自己不同的颜色，最终图应该被划分为黑色点和白色点两部分，每一条边两边的颜色都不同，如果有一个点既该是黑色也该是白色则不是二分图
    3、实际实现时，可能图不连通，需要对每个连通块都染色判断。染色通过 DFS 实现，初始化颜色为 $-1$ 表示未被染色，每个连通块第一个点初始染 $0$，后续点通过 $col[x] \oplus 1$ 获取当前点不同的颜色

  • 代码实现

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

const int N = 2e5 + 10;

vector<int> g[N]; // 建图
int col[N];       // 染色

// DFS 进行染色，返回该连通块是否是二分图
bool DFS(int x)
{
    for (auto y : g[x])
    {
        // 未被染色，需要染色
        if (col[y] == -1)
        {
            // 与 x 不同的颜色
            col[y] = col[x] ^ 1;

            // 如果 y 染色失败，返回 false
            if (!DFS(y))
                return false;
        }
        // 如果 y 与 x 颜色相同，返回 false
        else if (col[y] == col[x])
            return false;
    }

    return true;
}

void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    // 初始化 col 为 -1 表示未被染色
    for (int i = 1; i <= n; i++)
        col[i] = -1;

    bool ans = true;

    // 枚举所有点
    for (int i = 1; i <= n; i++)
    {
        // 如果未被染色，说明整个连通块未被染色
        if (col[i] == -1)
        {
            col[i] = 0;    // 设置该点为起始颜色
            ans &= DFS(i); // 对整个连通块 DFS 染色
        }
    }

    cout << (ans ? "YES" : "NO");
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

匈牙利算法(最大匹配)

  • 匈牙利算法

    1、情人节：有 $n$ 个男生 $m$ 个女生($n,m \leq 3 \times 10^3$)，给出 $k$ 对暧昧关系 $x, y$，表示男生 $x$ 与女生 $y$ 可能成为情侣，问最多能匹配多少对情侣
    2、匈牙利算法(增广路算法，最大匹配)：在二分图中(该题可看作二分图，男生看作左边的点，女生看作右边的点)，匈牙利算法遵循一个原则，当左点(男生)试图匹配的右点(女生)被占据，会试图赶走原主(原先匹配的左点)，如果原主有其他替代则会找替代，否则不动
    3、实现中，建图时只需要存从左往右的边。DFS 返回左点能否成功匹配，用一个 $p[]$ 存储右点当前所匹配的左点编号，按上述原则设计 DFS。其中需要 $vis$ 标记当前这轮左点的匹配过程中，右点被走过的情况，注意每次开始新的左点匹配需要重置
    4、由于 $vis$ 的清空操作处复杂度较高，可以引入一个时间戳 $dfn$，并将 $vis$ 改为 int 型。每轮判断 $vis$ 改为判断 $vis$ 是否值为时间戳，标记 $vis$ 也同理，这样在新的一轮匹配时，只需要更新 $dfn$ 而不必清空整个 $vis$。优化后代码在代码实现部分后展示
    5、Konig 定理(最小点覆盖)：从二分图中选择最少的点，使得每条边至少有一个端点被选，则最少的点的个数等于最大匹配数。

  • 代码实现

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

const int N = 3e3 + 10;

vector<int> g[N];
int p[N]; // p[i] 表示右点(女生) i 所匹配的左点(男生)的编号
bitset<N> vis;

// 返回左点能否匹配
bool DFS(int x)
{
    // 枚举所有暧昧对象
    for (auto &y : g[x])
    {
        // 如果被走过就跳过，否则标记当前 y 这一轮左点被走过
        if (vis[y])
            continue;
        vis[y] = true;

        // 如果未被占有，或者能够让原主再找到另外一个，则自己占有
        if (!p[y] || DFS(p[y]))
        {
            p[y] = x;
            return true;
        }
    }

    // 所有暧昧对象都不行，返回 false
    return false;
}

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;

    // 建图，只需要存从左往右的边
    for (int i = 1; i <= k; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
    }

    int ans = 0;
    // 枚举所有左点(男生)
    for (int i = 1; i <= n; i++)
    {
        // 每一次清空 vis
        vis.reset();

        // 跑 DFS 统计当前左点能否匹配
        if (DFS(i))
            ans++;
    }
    cout << ans;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

  • 优化后代码

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

const int N = 3e3 + 10;

vector<int> g[N];
int p[N];        // p[i] 表示右点(女生) i 所匹配的左点(男生)的编号
int vis[N], dfn; // vis 与 时间戳 dfn

// 返回左点能否匹配
bool DFS(int x)
{
    // 枚举所有暧昧对象
    for (auto &y : g[x])
    {
        // 改为判断值是否是 dfn，如果被走过就跳过，否则标记当前 y 这一轮左点被走过
        if (vis[y] == dfn)
            continue;
        vis[y] = dfn;

        // 如果未被占有，或者能够让原主再找到另外一个，则自己占有
        if (!p[y] || DFS(p[y]))
        {
            p[y] = x;
            return true;
        }
    }

    // 所有暧昧对象都不行，返回 false
    return false;
}

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;

    // 建图，只需要存从左往右的边
    for (int i = 1; i <= k; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
    }

    int ans = 0;
    // 枚举所有左点(男生)
    for (int i = 1; i <= n; i++)
    {
        // 每一次增加 dfn
        dfn++;

        // 跑 DFS 统计当前左点能否匹配
        if (DFS(i))
            ans++;
    }
    cout << ans;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

页底评论