首页 > 其他分享 >「WOJ 4701」Walk 虚点建图+01bfs

「WOJ 4701」Walk 虚点建图+01bfs

时间:2022-11-23 13:34:15浏览次数:44  
标签:le dist 4701 val int Walk vis 建图 id

前言

模拟赛中,yzh遇到了这道题,但由于yzh没有学过01bfs。。。所以就一直在优化这道题,导致浪费了很长时间 (但nfls的数据太水,dij和spfa都能过)

Description

给你一个 \(n\) 个点,\(m\) 条边的图,经过每条边需要消耗 \(1\) 的时间。

每个点还会有一个权值 \(val_i\) 。使得

任意两个房间 \(u,v\) 可以消耗 \(1\) 的时间传送,当且仅当 \(val_u \&val_v=val_v\)

其中 \(\&\) 为运算。

现在,你站在 \(1\) 点,你需要求出从 \(1\) 号点到达每一个点,所需要的最短时间。

输入格式

第一行 \(n,m\)。

第二行 \(n\) 个数,代表 \(val_1,val_2,\cdots,val_n\)。

接下来 \(m\) 行,每行 \(u,v\) 表示一条从 \(u\) 到 \(v\) 的有向边。

输出格式

输出 \(n\) 行。第 \(i\) 行输出从 \(1\) 到 \(i\) 所消耗的最小时间。

数据范围

\[1\le n\le 2\times 10^5\\ 1\le m\le 3\times 10^5\\ 1\le val_i\le 2^{30} \]

Solution

暴力

有一种暴力的做法,我们可以暴力枚举每两个节点的 \(val\)。并对其进行连边,然后跑一遍bfs。这样做边的数量会非常多,显然不能拿全分。

优化建边

考虑优化建边,不难想到,建若干个虚点 \(x\) ,我们只需要将 \(val=x\) 的节点向 \(x\) 连一条长度为 \(0\) 的边即可,然后对于两个不同的虚点,若满足 \(x\&x'=x'\) 那么虚点 \(x\) 向 \(x'\) 连一条长度为 \(0\) 的有相边。这样做显然还是有很多边因为 \(1\le val_i\le 2^{30}\)。

考虑继续优化建边,类似于高维前缀和的做法,对于两个虚点 \(x\) 和 \(x'\),满足 \(x\oplus x'=2^k(k\epsilon \mathbb N)\) ,那么 \(x\) 向 \(x'\) 连一条长度为 \(0\) 的有向边,可以把这种优化建边理解为一种树形结构。比如 \((111)_2\) 向 \((110)_2\) 连边,\((110)_2\) 向 \((100)_2\) 连边,那么就相当于 \((111)_2\) 到 \((100)_2\) 连了一条长度为 \(0\) 的边。

求最短路——01bfs

建完边考虑如何求最短路,由于边长既有 \(1\) 也有 \(0\) 所以普通的bfs是肯定不行的,我们可以用dij进行求最短路,但可能会不过了 (但也能卡过),对于虚点建图显然是一个较为稀疏的图,spfa实测跑的比dij快。正确解法是01bfs,具体的,队列队头的点,将它延申出去的边中长度为 \(0\) 的边的结束点先放入队头,再将长度为 \(1\) 的放入队尾,显然的,这样就能够使得求出来的长度最小了,这个01bfs的过程可以用deque实现

CODE

01bfs 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 998244353, N = (1 << 20) + (1000000) + 1000, T = (1 << 20), inf = 0x3f3f3f3f;
int val[N];
struct node {
    int id, v;
};
vector<node> a[N];
int lowbit(int x) { return x & (-x); }
int dis[N];
deque<node> q;
bool vis[N];
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    int mx = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &val[i]);
        mx = max(mx, val[i]);
        a[val[i]].emplace_back(node{ i + T, 0 });
        a[i + T].emplace_back(node{ val[i], 1 });
    }
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        a[u + (T)].emplace_back(node{ v + T, 1 });
        //	a[v + T].emplace_back(node{u + T , 1});
    }
    for (int i = 1; i < (T); i++) {
        int t = i;
        for (; t >= 1; t -= lowbit(t)) {
            if (i - lowbit(t) == 0)
                break;
            a[i].emplace_back(node{ i - lowbit(t), 0 });
        }
    }
    memset(dis, 0x3f, sizeof(dis));
    q.push_front(node{ 1 + T, 0 });
    dis[1 + T] = 0;
    while (!q.empty()) {
        node u = q.front();
        q.pop_front();
        if (vis[u.id])
            continue;
        vis[u.id] = true;
        for (auto v : a[u.id]) {
            if (vis[v.id])
                continue;
            if (v.v == 0)
                q.push_front(node{ v.id, u.v }), dis[v.id] = min(dis[v.id], u.v);
            if (v.v == 1)
                q.push_back(node{ v.id, u.v + 1 }), dis[v.id] = min(dis[v.id], u.v + 1);
        }
    }
    for (int i = 1 + T; i <= n + T; i++) {
        if (dis[i] == inf)
            puts("-1");
        else
            printf("%d\n", dis[i]);
    }
    return 0;
}

dij代码

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 7;
const int MAXN = (1 << 20);
int n, m;
int valt[N];
vector<int> edge[N];
vector<int> node[MAXN + 7];
int dist[N + MAXN];
bool vis[N + MAXN];
priority_queue<pii, vector<pii>, greater<pii> > qu;
// int pre[N+MAXN];
void dij() {
    memset(dist, inf, sizeof(dist));
    dist[1] = 0;
    qu.push(make_pair(0, 1));
    while (!qu.empty()) {
        int u = qu.top().second;
        // cout<<u<<endl;
        int minn = qu.top().first;
        qu.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        if (u <= n) {
            for (int i = 0; i < edge[u].size(); ++i) {  //常规m条边
                int v = edge[u][i];
                if (dist[v] > minn + 1 && !vis[v]) {
                    dist[v] = minn + 1;
                    qu.push(make_pair(dist[v], v));
                }
            }
            if (!vis[valt[u] + n]) {
                qu.push(make_pair(minn, valt[u] + n));
                // if(valt[u]==6655)
                //     cout<<u<<endl;
            }
            continue;
        }
        u -= n;
        for (int i = 0; i < node[u].size(); ++i) {  //点权为u的点
            int v = node[u][i];
            if (dist[v] > minn + 1 && !vis[v]) {
                dist[v] = minn + 1;
                qu.push(make_pair(dist[v], v));
                // if(v==3) cout<<u<<"->"<<dist[v]<<endl;
            }
        }
        for (int i = 0; i <= 20; ++i) {  //虚点之间连边
            if (((u >> i) & 1)) {
                int v = (u ^ (1 << i));
                if (v == 0)
                    continue;
                if (dist[v + n] > minn && !vis[v + n]) {
                    dist[v + n] = minn;
                    qu.push(make_pair(minn, v + n));
                    // if(v==6655){
                    //     cout<<u<<";;;\n";
                    // }
                }
            }
        }
    }
}
signed main() {
    clock_t st, ed;
    st = clock();
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &valt[i]);
        node[valt[i]].push_back(i);
    }
    for (int i = 1; i <= m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        edge[u].push_back(v);
    }
    dij();
    for (int i = 1; i <= n; ++i) {
        if (dist[i] == inf) {
            puts("-1");
            continue;
        }
        printf("%d\n", dist[i]);
    }
    ed = clock();
    // cout<<endl<<"run:"<<ed-st<<"ms"<<endl;
    return 0;
}

标签:le,dist,4701,val,int,Walk,vis,建图,id
From: https://www.cnblogs.com/I-am-yzh/p/16917933.html

相关文章

  • 5分钟搭建图片压缩应用
    摘要:用华为云函数工作流FunctionGraph搭建图片压缩应用。本文分享自华为云社区《真正的按需计费丨函数工作流FunctionGraph实战,5分钟搭建图片压缩应用》,作者:华为云PaaS服......
  • 题解:【ABC245F】Endless Walk
    题目链接本题解适合像我这样的不具备思维能力的选手。首先根据题意,一个点如果符合要求,那它必然在一个点数大于\(2\)的强联通分量里,因为如果只有一个点它就哪里都去不了......
  • 补档--【THM】Walking An Application(遍历web应用程序)-学习
    本文相关的TryHackMe实验房间链接:https://tryhackme.com/room/walkinganapplication通过学习相关知识点:仅使用你的浏览器开发工具手动检查Web应用程序的安全问题,仅使用......
  • 20221111_T1B_线段树优化建图/并查集
    题意给定一个字符串,其中只有a和b,现在一个字符能够跳到与之中间a的个数范围在\([l,r]\)的东西。题解赛时得分:100/100对于一个东西,显然如果将能相互到达连边,那么......
  • HDU 3355 Hop — Don’t Walk!
    ProblemDescriptionKERMITTHEFROGisaclassicvideogamewithasimplecontrolandobjectivebutrequiresagooddealofthinking.Youcontrolanani......
  • VulnHub-Lampiao-Walkthrough
    nmap扫描内网存活主机nmap-sP192.168.32.0/24我的靶机ip是192.168.32.135扫描端口nmap-sS-sV-A-p-192.168.32.135扫出来22、80、1898端口这里对80网站源码......
  • VulnHub-GoldenEye-1-Walkthrough
    靶机地址:https://www.vulnhub.com/entry/goldeneye-1,240/下载成功过后使用虚拟机打开需要注意:靶机和kail的网络适配器需要一致,不然会扫描不出来,这里我使用的的nat模式......
  • ASP.NET Core 集成 Skywalking 实现链路追踪
    Skywalking部署Skywalking简单介绍Skywalking是一个应用性能管理(APM)系统,具有服务器性能监测,应用程序间调用关系及性能监测等功能,Skywalking分为服务端、管理界面、以及......
  • 学习笔记-Bandit-WalkThrough
    Bandit-WalkThrough免责声明本文档仅供学习和研究使用,请勿使用文中的技术源码用于非法用途,任何人造成的任何负面影响,与本人无关.https://overthewire.org/wargames......
  • 学习笔记-PumpkinRaising-WalkThrough
    PumpkinRaising-WalkThrough免责声明本文档仅供学习和研究使用,请勿使用文中的技术源码用于非法用途,任何人造成的任何负面影响,与本人无关.靶机地址https://www.vu......