首页 > 代码库 > bzoj 1040 骑士
bzoj 1040 骑士
这题真不爽,各种WA,写个题解浏览器还挂了,真不爽。
所以不多说了,就说关于判断是否是父节点的问题,不能直接判,会有重边,这种情况只能用编号判,传进去入边的编号,(k^1) != fa,这样就可以了。
要注意的细节很多啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊!
上代码:
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#include <queue>#include <stack>#define N 1000100using namespace std;int n, power[N];int p[N] = {0}, next[N*2], v[N*2], bnum = -1;long long f1[N][2] = {0}, f2[N][2] = {0};void addbian(int x, int y){ bnum++; next[bnum] = p[x]; p[x] = bnum; v[bnum] = y; bnum++; next[bnum] = p[y]; p[y] = bnum; v[bnum] = x;}int root, ban;int cannot;bool vis[N] = {0};void dfs(int now, int fa){ int k = p[now]; while (k != -1) { if ((k^1) != fa && v[k] != ban) { if (vis[v[k]]) { root = v[k]; ban = now; cannot = k^1; } else { vis[v[k]] = 1; dfs(v[k], k); } } k = next[k]; }}void makeans_root(int now, int fa){ int k = p[now]; if (now == ban) { while (k != -1) { if ((k^1) != fa && v[k] != root) { makeans_root(v[k], k); f1[now][0] += max(f1[v[k]][0], f1[v[k]][1]); f1[now][1] += f1[v[k]][0]; } k = next[k]; } return; } f1[now][1] = power[now]; while (k != -1) { if ((k^1) != fa && k != cannot) { makeans_root(v[k], k); f1[now][0] += max(f1[v[k]][0], f1[v[k]][1]); f1[now][1] += f1[v[k]][0]; } k = next[k]; } return;}void makeans_ban(int now, int fa){ int k = p[now]; if (now == ban) { f2[now][1] = power[now]; while (k != -1) { if ((k^1) != fa && v[k] != root) { makeans_ban(v[k], k); f2[now][0] += max(f2[v[k]][0], f2[v[k]][1]); f2[now][1] += f2[v[k]][0]; } k = next[k]; } return; } f2[now][1] = power[now]; while (k != -1) { if ((k^1) != fa && k != cannot) { makeans_ban(v[k], k); f2[now][0] += max(f2[v[k]][0], f2[v[k]][1]); f2[now][1] += f2[v[k]][0]; } k = next[k]; } return;}int main(){ scanf("%d", &n); for (int i = 1; i <= n; ++i) p[i] = -1; for (int i = 1; i <= n; ++i) { int x; scanf("%d%d", &power[i], &x); addbian(x, i); } long long ans = 0; for (int i = 1; i <= n; ++i) if (!vis[i]) { root = -1; ban = -1; vis[i] = 1; dfs(i, -1); makeans_root(root, -1); makeans_ban(root, -1); long long zans = 0; zans = max(f1[root][1], zans); zans = max(zans, f1[root][0]); zans = max(f2[root][0], zans); ans += zans; } printf("%lld\n", ans);}
bzoj 1040 骑士
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。