首页 > 代码库 > hdu 4858 项目管理 图分治 (复合算法)
hdu 4858 项目管理 图分治 (复合算法)
hdu 4858 项目管理
题意:给n(<=100000)个点,m条边( <=n+10),可能有重边,每个点有个值val,初识为0。
2种操作。
操作1:点x的值,加addx。
操作2:输出x点的邻点的val和。
分析:简单的优化操作1或操作2是不行的。
法一:针对点的度将图中点分为两类点。对于度大于sqrt (n)的点为重点,对于小于等于sqrt(n)的点为轻点。 重点的个数小于sqrt(n)个。针对重点和轻点分别处理。
法二:也可考虑每个点,将其邻点分类。大于该点度的点分为一类,等于该点的度的分为一类,小于该点的度的点分为一类。分别处理。
法一:
const int maxn = 100100; vector<int>v[maxn], vgt[maxn]; int d[maxn]; int val[maxn]; int sum[maxn]; int n, m; const int MM = 3333; int main () { int T; cin >> T; while (T--) { scanf("%d%d", &n, &m); memset(d, 0, sizeof(d)); memset(val, 0, sizeof(val)); memset(sum, 0, sizeof(sum)); for (int i = 1; i <= n; i++) { v[i].clear(); vgt[i].clear(); } for (int i = 0; i < m; i++) { int x, y; scanf("%d%d", &x, &y); v[x].push_back(y); v[y].push_back(x); d[x]++; d[y]++; } for (int i = 1; i <= n; i++) { for (int j = 0; j < v[i].size(); j++) { int r = v[i][j]; if (d[r] > MM) vgt[i].push_back(r); } } int Q; cin >> Q; while (Q--) { int op; int x, addx; scanf("%d", &op); if (!op) { scanf("%d%d", &x, &addx); val[x] += addx; if (d[x] <= MM) { for (int i = 0; i < vgt[x].size(); i++) { int y = vgt[x][i]; sum[y] += addx; } } } else { scanf("%d", &x); int ans = 0; if (d[x] <= MM) { for (int i = 0; i < v[x].size(); i++) { ans += val[v[x][i]]; } } else { ans += sum[x]; for (int i = 0; i < vgt[x].size(); i++) { int y = vgt[x][i]; ans += val[y]; } } printf("%d\n", ans); } } } return 0; } /** 4 3 2 1 2 1 3 6 0 1 15 0 3 4 1 1 1 3 0 2 33 1 2 3 2 1 2 1 2 6 0 1 15 1 1 0 2 15 1 1 1 3 */
const int maxn = 100100; vector<int>v[maxn], vgt[maxn], veq[maxn]; int d[maxn]; int val[maxn]; int sum[maxn]; int n, m; const int MM = 3333; int main () { int T; cin >> T; while (T--) { scanf("%d%d", &n, &m); memset(d, 0, sizeof(d)); memset(val, 0, sizeof(val)); memset(sum, 0, sizeof(sum)); for (int i = 1; i <= n; i++) { v[i].clear(); vgt[i].clear(); veq[i].clear(); } for (int i = 0; i < m; i++) { int x, y; scanf("%d%d", &x, &y); v[x].push_back(y); v[y].push_back(x); d[x]++; d[y]++; } for (int i = 1; i <= n; i++) { for (int j = 0; j < v[i].size(); j++) { int r = v[i][j]; if (d[r] > d[i]) vgt[i].push_back(r); else if (d[r] == d[i]) veq[i].push_back(r); } } int Q; cin >> Q; while (Q--) { int op; int x, addx; scanf("%d", &op); if (!op) { scanf("%d%d", &x, &addx); val[x] += addx; for (int i = 0; i < vgt[x].size(); i++) sum[vgt[x][i]] += addx; } else { scanf("%d", &x); int ans = sum[x]; for (int i = 0; i < vgt[x].size(); i++) ans += val[vgt[x][i]]; for (int i = 0; i < veq[x].size(); i++) ans += val[veq[x][i]]; printf("%d\n", ans); } } } return 0; } /** 4 3 2 1 2 1 3 6 0 1 15 0 3 4 1 1 1 3 0 2 33 1 2 3 2 1 2 1 2 6 0 1 15 1 1 0 2 15 1 1 1 3 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。