Skip to content

Latest commit

 

History

History
249 lines (214 loc) · 5.41 KB

信息传递.md

File metadata and controls

249 lines (214 loc) · 5.41 KB
Raw

信息传递

题目

by Chen Ning

描述

已知有 N 个节点, 初始信息由 0 号节点开始发送. 给定 M 条可能毁坏的信道, 需要依次考虑只有一条信道被毁坏时是否所有节点仍能收到 0 号节点发送的信息.

IO格式

输入:

N M
0号结点邻接点个数 0号结点邻接点...
...
第1条可能毁坏信道起点 第1条可能毁坏信道终点
...

输出:

// 连通 = 1, 未连通 = 0
未毁坏是否连通
毁坏第1条信道是否连通
...

样例

输入:

4 2
2 1 2
2 2 3
0
1 0
0 1
0 2

输出:

1
0
1

解答

思路

很轻易地想到使用 BFS 来遍历图:

  • 如果无法连通, 则全输出 0;
  • 如果可以连通, 先输出 1, 然后对每条可能缺损信道进行遍历:
    • 如果终点为 0, 输出 1;
    • 如果终点不为 0, 但入度为 1, 输出 0;
    • 否则, 进行 BFS 遍历.

关于图的存储: 为了防止出现指针内存分配失败的情况, 采用一整条数组 array<ui, EMAX> adjs 来存储邻接表, 并用 array<Node, NMAX> nodes 来分割. 对于一个结点 ui i, 其邻接表为 adjs[nodes[i].sub : nodes[i].sub + nodes[i].len].

代码

#include <array>
#include <cstdio>
using namespace std;

#define prf printf
#define scf scanf
using ui = unsigned int;

constexpr size_t NMAX = 65538;
constexpr size_t MMAX = 65538;
constexpr size_t EMAX = 1048578;

struct Node {
    ui inDeg;  // 入度
    ui sub;    // adjs起始下标
    ui len;    // adjs长度
};

struct Destroy {
    ui sub_nodes;
    ui sub_adjs;
};

ui N;
array<ui, EMAX> adjs;     // 邻接表
array<Node, NMAX> nodes;  // 结点表
ui M;
array<Destroy, MMAX> dess;  // 可能毁坏信道表

template <typename T>
struct queue {
    queue() : head(0), rear(0){};
    array<ui, NMAX> _q;
    ui head;
    ui rear;
    T front() { return _q[head]; };
    bool empty() { return head == rear; };
    void pop() { head = (head + 1) % NMAX; };
    void push(T _val) {
        _q[rear] = _val;
        rear = (rear + 1) % NMAX;
    };
};

void inputGraph() {
    scf("%u%u", &N, &M);
    auto k = 0;
    for (auto i = 0u; i < N; i++) {
        nodes[i].sub = k;
        scf("%u", &nodes[i].len);
        for (auto j = 0u; j < nodes[i].len; j++) {
            scf("%u", &adjs[k]);
            nodes[adjs[k]].inDeg++;
            k++;
        }
    }
    for (auto i = 0u; i < M; i++) {
        scf("%u", &dess[i].sub_nodes);
        ui targetNode;
        scf("%u", &targetNode);
        auto& startNode = nodes[dess[i].sub_nodes];
        auto sub_stop = startNode.sub + startNode.len;
        for (auto j = startNode.sub; j < sub_stop; j++) {
            if (adjs[j] == targetNode) {
                dess[i].sub_adjs = j;
                break;
            }
        }
    }
}

bool bfsAll() {
    array<bool, NMAX> visited{true};
    ui visitCount = 1;
    queue<ui> q;
    q.push(0);
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        if (!visited[cur]) {  // 未遍历过
            visited[cur] = true;
            visitCount++;
        }
        auto& curNode = nodes[cur];
        auto sub_stop = curNode.sub + curNode.len;
        for (auto i = curNode.sub; i < sub_stop; i++) {
            if (!visited[adjs[i]]) {  // 未遍历过且未入队
                visited[adjs[i]] = true;
                visitCount++;
                q.push(adjs[i]);
            }
        }
    }
    return visitCount == N;
}

bool bfsOne(ui target, Destroy& des) {
    array<bool, NMAX> visited{true};
    queue<ui> q;
    q.push(0);
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        if (!visited[cur]) visited[cur] = true;
        auto& curNode = nodes[cur];
        auto sub_stop = curNode.sub + curNode.len;
        if (cur == des.sub_nodes) {  // 存在缺损信道
            for (auto i = curNode.sub; i < sub_stop; i++) {
                if (i == des.sub_adjs) continue;
                auto curAdj = adjs[i];
                if (curAdj == target) return true;
                if (!visited[curAdj]) q.push(curAdj);
            }
        } else {
            for (auto i = curNode.sub; i < sub_stop; i++) {
                auto curAdj = adjs[i];
                if (curAdj == target) return true;
                if (!visited[curAdj]) q.push(curAdj);
            }
        }
    }
    return false;
}

int main() {
    inputGraph();
    if (!bfsAll()) {
        prf("0");
        for (auto i = 0u; i < M; i++) prf("\n0");
        return 0;
    }
    prf("1");
    for (auto i = 0u; i < M; i++) {
        auto& des = dess[i];
        auto desAdj = adjs[des.sub_adjs];
        if (desAdj == 0) {  // 指向0无影响
            prf("\n1");
            continue;
        }
        if (nodes[desAdj].inDeg <= 1) {  // 入度少于1
            prf("\n0");
            continue;
        }
        if (bfsOne(desAdj, des))
            prf("\n1");
        else
            prf("\n0");
    }
    return 0;
}

时空消耗

1	Accepted	0 ms	792 KB
2	Accepted	0 ms	776 KB
3	Accepted	0 ms	784 KB
4	Accepted	88 ms	4696 KB
5	Accepted	4 ms	1128 KB
6	Accepted	56 ms	3008 KB
7	Accepted	36 ms	2648 KB
8	Accepted	0 ms	840 KB
9	Accepted	108 ms	2904 KB
10	Accepted	772 ms	2384 KB