CarryNotKarry

  • 首页
  • 语言学习
    • C++程序设计
    • 汇编语言
    • Python
  • 比赛总结
  • ACM-ICPC
    • 动态规划
    • 字符串
    • 搜索
    • 数学
    • 数据结构
    • 图论
    • 计算几何
    • 杂项
  • 分享
  • 上课内容
  • 其他
Carry
CUGBACMer/皇马球迷/C罗人迷
  1. 首页
  2. ACM-ICPC
  3. 图论
  4. 正文

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

2022年7月9日 363点热度 0人点赞 0条评论

题目

题目来源于北华大学计算机程序设计算法提高训练营个人赛的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的最短距离。

举个例子:

img

我一开始选取所有的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;
    }
}
标签: BFS 图论 多源BFS
最后更新:2022年7月12日

Carry

来自于湖南长沙

点赞
< 上一篇
下一篇 >

文章评论

取消回复
标签
BFS 图论 多源BFS
文章目录
  • 题目
  • 思路
  • 代码
其他文章

Carry爱三进制题解

【区间DP】POJ2955.Brackets

Codeforces Educational Round 122(Rated for Div.2)比赛总结 (rating+77)

汇编语言 实验四 子程序结构

汇编语言 实验三 循环结构和分支结构程序设计

C++程序设计

【基环树+思维】AcWing 1738.蹄球——每日一题2.6

AtCoder Beginner Contest 238比赛总结

【算法学习】线性基

【线性基】[BJWC2011]元素题解

From Carry
  • 在下不才,本博客也是为了记录自己的成长,并非成为非常专业的博客。
  • 如果有能够帮助你的地方是我最大的荣幸,一起加油吧!

ECNU-My love

THEME KRATOS MADE BY VTROIS