Skip to content

HDU4858 项目管理#

目录#

1. 题目描述#

1.1. Limit#

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

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

1.2. Problem Description#

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

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

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

1.3. Input#

第一行一个整数 ,表示测试数据的个数。 然后对于每个测试数据，第一行有两个整数 和 ，分别表示点数和边数。

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

然后一个整数 。

然后 行，每行第一个数 表示操作类型。如果 为 ，那么接下来两个数 表示给项目 的能量值加上 。 如果 为 ，那么接下来一个数 表示询问 相邻的项目的能量值之和。

所有点从 到 标号。

1.4. Output#

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

1.5. Sample Input#

1
3 2
1 2
1 3
6
0 1 15
0 3 4
1 1
1 3
0 2 33
1 2

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]);
            }
        }
    }
}

联系邮箱：curren_wong@163.com

Github：https://github.com/CurrenWong

欢迎转载/Star/Fork，有问题欢迎通过邮箱交流。

Back to top