MYF

HDU 4858 项目管理

Posted on | In | | Visitors

题目链接

HDU 4858

方法：邻接表水题

题目分析

解析

用vector记录对于节点u的所有邻接点v，push_back进g[u]中，然后将所有节点的能量存入数组e[]中，每次求u的邻接点之和只需要将g[u]的所有节点取出来，然后找这些节点的能量，累加即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define PI acos(-1)
#define rt(n)       (i==n?'\n':' ')
#define debug         printf("Hi----------\n")
#define eps 1e-8
#define INF 0x3f3f3f3f
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
#define maxn 10005
vector<ll>g[100005];
ll e[100005];
int u,v,n,m;
inline void scan(int &x)
{
    char c; for(c = getchar();c < '0' || c > '9';c = getchar());    x = c - '0';
    for(c = getchar();c >= '0' && c <= '9';c = getchar())   x = (x << 1) + (x << 3) + c - '0';
}
void init(){
    for (int i=0; i<=n; i++) {
        g[i].clear();
        e[i]=0;
    }
}
int main(){
    int T,c;
    scanf("%d",&T);
    while (T--) {
        ll ans=0;
        scanf("%d%d",&n,&m);
        init();
        while (m--) {
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        
        scan(m);
        while (m--) {
            scan(c);
            if (c==0) {
                scan(u),scan(v);
                e[u]+=v;
            }
            else{
                ans=0;
                scan(u);
                int sz=g[u].size();
                for (int i=0; i<sz; i++) {
                    ans+= e[g[u][i]];
                }
                printf("%lld\n",ans);
            }
                
        }
    }
}