牛客小白月赛43

F - 全体集合

https://ac.nowcoder.com/acm/contest/11220/F

时间限制:C/C++ 2秒,其他语言4秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld

题目描述

给出 $n$ 个点 $m$ 条边 的无向图,给出 $k$ 个点,这 $k$ 个点上每个点都有一个人,每个人每回合能走到一个相邻的节点(不能停留不走),问:有没有可能在某一个回合,让这些人都集中在一个点?

输入描述:

第一行包含三个整数 $n$ $m$ $k$ ,$1\le n,k\le 2e5$,$0\le m\le min(5e5,n*(n-1)/2)$。

接下来 $m$ 行,每行包括两个整数 $u$ $v$,表示存在一条从节点 $u$ 到 $v$ 的边,节点编号从 $1$ 开始,保证图联通,无重边,无自环。

接下来一行,包含 $k$ 个整数,分别表示有人所在的节点,保证 $k$ 个节点各不相同。

输出描述:

输出包括一行,如果有办法能让全部人都集中在一个点,输出”YES“,否则输出”NO“,不包含引号。

示例1

输入

3 2 2
1 2
2 3
1 3

输出

YES

说明

第一回合,让节点 $1$ 的人走到节点 $2$,节点 $3$ 的人走到节点 $2$ ,全都集中了,输出YES

示例2

输入

3 2 2
1 2
2 3
1 2

输出

NO

说明

由于每回合不能不移动,不存在一种走法让全部人集中。

我的笔记

分析

问题转化

容易发现,如果每个人之间的路程长度为偶数,那么所有人一定可以集中到一起。距离近的人集中后,可以“左右横跳”来等剩下的人集中,因为每个人距离是偶数,左右横跳需要 2 步,所以可以保证所有人都集中到一起。如果有两个人之间的路程长度为奇数,那么他们将无法集中。因为“反复横跳”后,这两个人总是隔着一个距离,没法集中到一起。

所以题目问题就转化为:判断所有人两两之间是否都有偶数路径。还可进一步处理为:随意选择一个人,他和其他人是否都有偶数路径。

需要注意,两个人之间可以既存在奇数路程,也存在偶数路程,因为图可以连接成网,选取不同的路径,路程长度可以不同。

算法选择

可以先随意选择一个人(源码中选择的是第一个人),然后用 BFS 将这个人与每个节点的路径种类(即,是否有偶数路径、技术路径)计算出来,最后遍历一遍有人的节点是否都有偶数路径即可。

注意点

这一题 BFS 的子节点比较特殊,并不是直接为节点序号。因为我们既要计算是否有偶数路径,也要计算是否有奇数路径,这样才能用 BFS ,即:上一个有奇数路径,这一个就有偶数路径;上一个有偶数路径,这一个就有奇数路径。

因此子节点用了一个二元组表示,每个节点序号包含两个子节点,一个用来判断奇数路径,一个用来判断偶数路径。父子节点的递推就是,若父节点判断的是奇数(偶数)路径,子节点就是判断所有与父节点连接的点的偶数(奇数)路径情况。

源码

#include <bits/stdc++.h>

using namespace std;

int n, m, k;
vector<int> connect[200010];
vector<int> people;
bool dis[200010][2];
queue<int> que;

void bfs(void)
{
    queue<pair<int, bool>> que;
    que.push({people[0], 0});
    while (!que.empty())
    {
        pair<int, bool> now = que.front();
        que.pop();
        for (int i = 0; i < connect[now.first].size(); i++)
        {
            pair<int, bool> next = {connect[now.first][i], now.second ? 0 : 1};
            if (!dis[next.first][next.second])
            {
                dis[next.first][next.second] = 1;
                que.push({next.first, next.second});
            }
        }
    }
}

int main(void)
{
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        connect[u].push_back(v);
        connect[v].push_back(u);
    }
    for (int i = 0; i < k; i++)
    {
        int t;
        scanf("%d", &t);
        people.push_back(t);
    }
    bfs();
    bool flag = true;
    for (int i = 0; i < people.size(); i++)
    {
        if (!dis[people[i]][0])
        {
            flag = false;
            break;
        }
    }
    if (flag)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
    return 0;
}

标签: 广度优先搜索

添加新评论