今日小结

1. BFS与最短路算法比较, BFS本质上就是边权为1的dijkstra;

2. 当所有边的权值都为1时, 优先考虑最短路;

3. 最短路不止能以节点为起点

P5663 [CSP-J2019] 加工零件

1. 每次询问点1能否恰好走L步到达点a;

2. 若1到a的最短路大于L, 直接无解;

3. 若1到a的最短路小于等于L, 可以折返凑L步但是需要d1[a]%2==L%2;

4. 维护点1到每个点i的奇数最短路d1[i]和偶数最短路d2[i];

5. 答案:

if (d1[a] % 2 == L % 2 && d1[a] <= L) cout << "Yes\n";
else if (d2[a] % 2 == L % 2 && d2[a] <= L) cout << "Yes\n";
else cout << "No\n";

6. BFS的改造

if (d1[j] > d2[t] + 1)
{
    d1[j] = d2[t] + 1;
    q.push(j);
}

if (d2[j] > d1[t] + 1)
{
    d2[j] = d1[t] + 1;
    q.push(j);
}

7. 不能使用标记数组, 因为一个点可能去多次;

8. 初始值 d1[1] = INF, d2[1] = 0

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

const int N = 1e5 + 10, M = 2e5 + 10, INF = 0x3f3f3f3f;
int h[N], e[M], ne[M], idx;
int d1[N], d2[N];

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

void bfs()
{
    memset(d1, 0x3f, sizeof d1);
    memset(d2, 0x3f, sizeof d2);

    d1[1] = 0;

    queue<int> q;

    q.push(1);

    while (q.size())
    {
        int t = q.front();
        q.pop();

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];

            if (d1[j] > d2[t] + 1)
            {
                d1[j] = d2[t] + 1;
                q.push(j);
            }

            if (d2[j] > d1[t] + 1)
            {
                d2[j] = d1[t] + 1;
                q.push(j);
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m, q;
    cin >> n >> m >> q;

    memset(h, -1, sizeof h);

    int a, b;
    while (m--)
    {
        cin >> a >> b;

        add(a, b);
        add(b, a);
    }

    bfs();

    int l;
    while (q--)
    {
        cin >> a >> l;

        if (l & 1)
            if (l >= d2[a]) cout << "Yes\n";
        else cout << "No\n";
        else if (l >= d1[a]) cout << "Yes\n";
        else cout << "No\n";
    }


    return 0;
}

CF1272E Nearest Opposite Parity

方法1

时间复杂度 $O(N•N)$

对于每一个点i, 向i-a[i]和i+a[i]连边, 并枚举i跑BFS

方法2

时间复杂度 $O(n)$

1. 建反边, 每个位置i找到最近的与a[i]奇偶不同的位置, 等价于从每个奇数和每个偶数去所有的其他位置;

2. 对于所有的奇数a[i], 跑多起点BFS, 偶数a[i]同理; 得到d1[i], d2[i]

3. 找答案, 枚举i, 若a[i]是奇数, 输出d2[i], 否则输出d1[i];

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

const int N = 2e5 + 10, M = 4e5 + 10;
int h[N], e[M], ne[M], idx;
int a[N];
int d1[N], d2[N];

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    memset(h, -1, sizeof h);

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];

        if (i - a[i] > 0) add(i - a[i], i);
        if (i + a[i] <= n) add(i + a[i], i);
    }

    memset(d1, -1, sizeof d1);

    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (a[i] & 1) q.push(i), d1[i] = 0;

    while (q.size())
    {
        int t = q.front();
        q.pop();

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];

            if (d1[j] == -1 || d1[j] > d1[t] + 1)
            {
                d1[j] = d1[t] + 1;
                q.push(j);
            }
        }
    }

    memset(d2, -1, sizeof d2);

    for (int i = 1; i <= n; i++)
        if (a[i] % 2 == 0) q.push(i), d2[i] = 0;

    while (q.size())
    {
        int t = q.front();
        q.pop();

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];

            if (d2[j] == -1 || d2[j] > d2[t] + 1)
            {
                d2[j] = d2[t] + 1;
                q.push(j);
            }
        }
    }

    for (int i = 1; i <= n; i++)
        if (a[i] & 1) cout << d2[i] << ' ';
        else cout << d1[i] << ' ';


    return 0;
}

AT_abc254_e [ABC254E] Small d and k

水题一道, 注意0 ≤ Ki ≤ 3, 我们每次广搜最多执行27步

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

const int N = 1.5e5 + 10, M = 4.5e5 + 10;
int h[N], e[M], ne[M], idx;
int d[N];
int n, m;

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

void bfs(int x, int k)
{
    for (int i = 1; i <= n; i++) d[i] = -1; // 注意不能使用memset, 每次初始化1.5e5次, 时间复杂度太高了

    queue<int> q;

    d[x] = 0;
    q.push(x);

    int res = 0;
    while (q.size())
    {
        int t = q.front();
        q.pop();

        if (d[t] > k) break; // 超过规定步数直接break

        res += t; // 每次加上每步的编号

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];

            if (d[j] == -1)
            {
                d[j] = d[t] + 1;
                q.push(j);
            }
        }
    }

    cout << res << '\n'; // 输出结束
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    memset(h, -1, sizeof h);

    int a, b;
    while (m--)
    {
        cin >> a >> b;

        add(a, b);
        add(b, a);
    }

    cin >> m;

    while (m--)
    {
        cin >> a >> b;

        bfs(a, b);
    }


    return 0;
}

CF986A Fair

暴力 时间复杂度$O(n)$

1. 对于每个点i跑bfs, 并统计首次出现的颜色数量cnt, 并累加距离;

2. 当cnt==s时, bfs结束, 并将累加的距离维护最小值ans;

优化:

3. 由于k<=100, 考虑每种颜色跑bfs

4. 对同一种颜色j, 跑多起点bfs, 求出该颜色到所有点i的距离d[i][j]

5. 求答案时, 对于点i, 去前s小的值相加, 维护最小值ans;

时间复杂度$O(N•K)$

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

const int N = 1e5 + 10, M = 110, INF = 0x3f3f3f3f;
int h[N], e[N << 1], ne[N << 1], idx;
int a[N];
int d[N][M];
int n, m, k, s;

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

void bfs(int color)
{   
    queue<int> q;

    for (int i = 1; i <= n; i++)
        if (a[i] == color)
        {
            q.push(i);
            d[i][color] = 0;
        }

    while (q.size())
    {
        int t = q.front();
        q.pop();

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];

            if (d[j][color] == -1)
            {
                d[j][color] = d[t][color] + 1;
                q.push(j);
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> k >> s;

    for (int i = 1; i <= n; i++) cin >> a[i];

    memset(h, -1, sizeof h);

    int a, b;
    while (m--)
    {
        cin >> a >> b;

        add(a, b);
        add(b, a);
    }

    memset(d, -1, sizeof d);

    for (int i = 1; i <= k; i++) bfs(i);

    for (int i = 1; i <= n; i++)
    {
        priority_queue<int, vector<int>, greater<int>> heap;

        for (int j = 1; j <= k; j++) heap.push(d[i][j]);

        int res = 0;
        for (int j = 0; j < s; j++)
        {
            res += heap.top();
            heap.pop();
        }

        cout << res << ' ';
    }


    return 0;
}