HDU4858 项目管理算法刷题笔记

文章目录

1. 题目描述
2. 解读
3. 代码

1. 题目描述

1.1. Limit

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

1.2. Problem Description

我们建造了一个大项目！这个项目有 $n$ 个节点，用很多边连接起来，并且这个项目是连通的！
两个节点间可能有多条边，不过一条边的两端必然是不同的节点。
每个节点都有一个能量值。

现在我们要编写一个项目管理软件，这个软件呢有两个操作：

给某个项目的能量值加上一个特定值。
询问跟一个项目相邻的项目的能量值之和。（如果有多条边就算多次，比如 $a$ 和 $b$ 有 $2$ 条边，那么询问 $a$ 的时候 $b$ 的权值算 $2$ 次）。

1.3. Input

第一行一个整数 $T (1 < = T < = 3)$ ,表示测试数据的个数。
然后对于每个测试数据，第一行有两个整数 $n (1 < = n < = 100000)$ 和 $m (1 < = m < = n + 10)$ ，分别表示点数和边数。

然后 $m$ 行，每行两个数 $a$ 和 $b$ ，表示 $a$ 和 $b$ 之间有一条边。

然后一个整数 $Q$ 。

然后 $Q$ 行，每行第一个数 $c m d$ 表示操作类型。如果 $c m d$ 为 $0$ ，那么接下来两个数 $u <mtext> </mtext> v$ 表示给项目 $u$ 的能量值加上 $v (0 < = v < = 100)$ 。
如果 $c m d$ 为 $1$ ，那么接下来一个数 $u$ 表示询问 $u$ 相邻的项目的能量值之和。

所有点从 $1$ 到 $n$ 标号。

1.4. Output

对每个询问，输出一行表示答案。

1.5. Sample Input

1.6. Sample Output

4
15
15

1.7. Source

BestCoder Round #1

2. 解读

看到题目中的节点和连边，我们很自然地会想到用图去存储，但是
节点最大数量是 10万，要存一个10万x10万的二维数组非常容易爆内存。而从题目中我们可以发现，这个图的连边是比较稀疏的，所以我们可以采用邻接表的方式进行存储。

用邻接表存储了点和连边的关系之后，我们再用一个数组去存储每一个节点的相邻节点能量之和。在某一个节点能量增加之后，增加所有与其相邻的节点的能量，有查询请求时直接输出即可。

我查了网上的一些其他解读，据说这里用到了一种算法叫做分块算法，感兴趣的同学可以了解一下。

3. 代码

#define mill 100010
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
int main()
{
    // test case
    int t;
    scanf("%d", &t);
    // Buffer
    long long list[mill];
    // 声明邻接表
    vector<int> vec_list[mill];
    for (int j = 0; j < t; j++) {
        // 清空邻接表
        memset(vec_list, 0, sizeof(vec_list));
        // 清空Buffer
        memset(list, 0, sizeof(list));
        // 读数据
        int n, m;
        scanf("%d %d", &n, &m);
        // 连边
        int a, b;
        // 循环m次，读入连边
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &a, &b);
            // ---存入ab-----------
            vec_list[a].push_back(b);
            // ---存入ba-----------
            vec_list[b].push_back(a);
        }
        // 读取query
        // query个数
        int q;
        scanf("%d", &q);
        // query 类型
        int qType;
        // query内容
        int u, v;
        // 读入query
        for (int i = 0; i < q; i++) {
            scanf("%d", &qType);
            if (qType == 0) {
                scanf("%d %d", &u, &v);
                // 操作query 0
                // 读连边
                vector<int> vec = vec_list[u];
                // 为每个与u相连的点加v能量
                for (unsigned long k = 0; k < vec.size(); k++) {
                    list[vec[k]] += v;
                }
            } else {
                scanf("%d", &u);
                // 操作query 1
                printf("%lld\n", list[u]);
            }
        }
    }
}