题目链接:
题意: 中文题诶~
思路:
解法1:暴力树剖
用一个数组 num[i] 维护编号为 i 的边当前最大能承受的重量. 在加边的过程中根据给出的父亲节点将当前边所在的链上所有边的num都减去当前加的边的重量, 注意当前边也要减自重. 那么当num首次出现负数时加的边号即位答案；
事实上这个算法的时间复杂度是O(n^2)的, 不过本题并没有出那种退化成单链的数据, 所以直接暴力也能水过；
代码:
1 #include2 #include 3 using namespace std; 4 5 const int MAXN = 5e4 + 10; 6 struct node{ 7 int c, w, pre; 8 }gel[MAXN]; 9 int num[MAXN];//num[i]为编号为i的绳子当前可以承受的最大重量10 11 int main(void){12 int n, ans = -1;13 scanf("%d", &n);14 for(int i = 0; i < n; i++){15 scanf("%d%d%d", &gel[i].c, &gel[i].w, &gel[i].pre);16 if(ans != -1) continue;17 num[i] = gel[i].c;18 int cnt = i;19 while(cnt != -1){20 num[cnt] -= gel[i].w;21 if(ans == -1 && num[cnt] <= -1) ans = i;22 cnt = gel[cnt].pre;//指向cnt的父亲节点23 }24 }25 if(ans == -1) cout << n << endl;26 else cout << ans << endl;27 return 0;28 }
解法2: 二分 + dfs
很显然在加边的过程中所有边的承受重量都是单调不减的, 那么可以考虑二分答案. 不过要注意判断函数的写法, 每一次判断都需要判断当前 mid条 边组成的树的所有边, 而不能只判断当前 mid 所在链上的边, 显然其他链上也可能存在不合法的边. 判断所有边的话可以 dfs 一遍, 回溯时判断即可.
代码:
1 #include2 #include 3 #include 4 #define ll long long 5 using namespace std; 6 7 const int MAXN = 5e4 + 10; 8 struct node{ 9 int c, w, pre;10 }gel[MAXN];11 vector sol[MAXN];12 bool flag;13 14 ll dfs(int u, int x){15 ll sum = gel[u].w;16 if(u > x) return 0;//mid边后面的不要算上去17 for(int i = 0; i < sol[u].size(); i++){18 sum += dfs(sol[u][i], x);19 }20 if(sum > gel[u].c && u) flag = false;//0是一个虚根,并没有对应的边21 return sum;22 }23 24 int main(void){25 int n;26 scanf("%d", &n);27 for(int i = 1; i <= n; i++){28 scanf("%d%d%d", &gel[i].c, &gel[i].w, &gel[i].pre);29 gel[i].pre++;30 sol[gel[i].pre].push_back(i);31 }32 int l = 1, r = n, cnt = n;33 while(l <= r){34 flag = true;35 int mid = (l + r) >> 1;36 dfs(0, mid);37 if(flag) cnt = mid, l = mid + 1;38 else r = mid - 1;39 }40 printf("%d\n", cnt);41 }
解法3: 并查集
记录每个节点的父节点
然后按输入顺序的倒叙 遍历每一个节点
计算以当前节点为根的子树的重量 ( 因为按照题目的输入顺序来说 当前节点要么没有子节点 要么子树已经遍历完 算入当前树的重量）
当遍历到某个节点时
当前节点与父节点的边无法承载当前节点为根的子树 便从输入序列最晚输入的节点开始删除
直到与父节点的边的能够承载当前节点为根的子树
又或者已经把遍历过的点都删除完了
这个过程中 用并查集维护某个节点 属于那一个跟节点 并且不断的压缩路径
每个条路径被压缩一次 均摊时间 就是边的数量 所以 这种做法很稳定的 O(n)
上面这段话是直接从讨论中复制过来的
代码:
1 #include2 #include 3 #include 4 #define ll long long 5 using namespace std; 6 7 const int MAXN = 1e5 + 10; 8 struct node{ 9 ll c, w, p;10 }gel[MAXN];11 12 ll ww[MAXN];13 vector vt[MAXN];14 int pre[MAXN], sol;15 16 int find(int x){17 return pre[x] == x ? x : pre[x] = find(pre[x]);18 }19 20 void update(int u){21 for(int i = 0; i < vt[u].size(); i++){22 gel[u].w += gel[vt[u][i]].w;23 pre[vt[u][i]] = u;24 }25 while(gel[u].w > gel[u].c){ //u即为当前根节点26 gel[find(sol)].w -= ww[sol];27 sol--;28 }29 }30 31 int main(void){32 int n;33 scanf("%d", &n);34 for(int i = 1; i <= n; i++){35 scanf("%lld%lld%lld", &gel[i].c, &gel[i].w, &gel[i].p);36 gel[i].p++;37 vt[gel[i].p].push_back(i);38 ww[i] = gel[i].w;//后面会对gel操作,所以需要先记录下gel的初始值来39 pre[i] = i;40 }41 sol = n;42 for(int i = n; i > 0; i--){43 update(i);44 }45 printf("%d\n", sol);46 return 0;47 }