北华大学2022校赛J-Darling（Hard）（图论/多源BFS）

题目

题目来源于北华大学计算机程序设计算法提高训练营个人赛的J题，邀请码:bhu2022。
给出一个$n(1\leq n\leq 10^6)$点$m$边的无向图每条边长为$1$，每个点拥有一个$0/1$的点权，0表示雌性，1表示雄性。一共有$q$次询问，每次询问x，回答距离点x最近的异性的最短距离是。

思路

考虑到数据范围比较大，肯定不能用暴力，所以需要用两遍bfs，一次从所有的0出发，去更新每个1点到0的最短距离；一次从所有的1出发，去更新每个0点到1的最短距离。

令f[i][0/1]，其中f[i][0]表示点i到0的最短距离，f[i][1]表示点i到1的最短距离。

举个例子：

我一开始选取所有的1进入队列，每次只传递到相邻的且异性的地方，并且没有走过（因为是bfs，所以一旦走过那么一定不能更新最短距离），然后让其加入队列，并且距离+1。

inline void bfs(int sex)
{
    queue<int> q;
    for (int i=1;i<=n;i++)
    {
        if (a[i]==sex)
            q.push(i),f[i][sex] = 0;//自己到自己性别距离当然为0
    }
    while (!q.empty())
    {
        int x = q.front();q.pop();
        for (int i=head[x];i;i=edge[i].next)
        {
            int y = edge[i].to;
            if (f[y][sex]==-1 && a[y]!=sex)
            {
                f[y][sex] = f[x][sex]+1;//等于上一次+1
                q.push(y);
            }
        }
    }
}

所以这个图我加入一开始是bfs(1)，也就是让3进入队列，更新f[3][1] = 0让其传递，当传到2的时候更新f[2][1] = f[3][1] + 1 = 1，这个意义也就是点2到1的最短距离为1，那么接下来是否会传递到1呢？会！因为1与3异性，也同样更新了f[1][1] = f[2][1] + 1 = 2

这样下来，我bfs(1)之后让所有的0都获得了到1的最短距离，同理，我再来一遍bfs(0)即可。最后读入$O(1)$输出答案即可。

代码

int f[N][2];
inline void bfs(int sex)
{
    queue<int> q;
    for (int i=1;i<=n;i++)
    {
        if (a[i]==sex)
            q.push(i),f[i][sex] = 0;
    }
    while (!q.empty())
    {
        int x = q.front();q.pop();
        for (int i=head[x];i;i=edge[i].next)
        {
            int y = edge[i].to;
            if (f[y][sex]==-1 && a[y]!=sex)
            {
                f[y][sex] = f[x][sex]+1;
                q.push(y);
            }
        }
    }
}
inline void Case_Test()
{
    cin>>n>>m>>q;
    for (int i=1;i<=n;i++) 
    {
        f[i][0] = f[i][1] = -1;
        cin>>a[i];
    }
    for (int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        add(u,v);add(v,u);
    }
    bfs(0);
    bfs(1);
    while (q--)
    {
        cin>>x;
        cout<<f[x][!a[x]]<<endl;
    }
}