51nod 1307 绳子与重物 （标记父节点更新即可）

1307 绳子与重物
基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题
有N条绳子编号 0 至 N - 1，每条绳子后面栓了一个重物重量为Wi，绳子的最大负重为Ci。每条绳子或挂在别的绳子下或直接挂在钩子上（编号-1）。如果绳子下所有重物的重量大于绳子的最大负重就会断掉（等于不会断）。依次给出每条绳子的负重Ci、重物的重量Wi以及绳子会挂在之前的哪条绳子的下面，问最多挂多少个绳子而不会出现绳子断掉的情况。

例如下图：

5, 2, -1
3, 3, 0
6, 1, -1
3, 1, 0
3, 2, 3

挂到第4个时会有绳子断掉，所以输出3。

Input
第1行：1个数N，表示绳子的数量(1 <= N <= 50000)。
第2 - N + 1行：每行3个数，Ci, Wi, Pi，Ci表示最大负重，Wi表示重物的重量，Pi表示挂在哪个绳子上，如果直接挂在钩子上则Pi = -1（1 <= Ci <= 10^9，1 <= Wi <= 10^9，-1 <= Pi <= N - 2)。
Output
输出1个数，最多挂到第几个绳子，不会出现绳子断掉的情况。
Input示例
5
5 2 -1
3 3 0
6 1 -1
3 1 0
3 2 3
Output示例
3

题目意思很明确了，就是绳子有最大载重，下面挂东西，问最多挂多少个不掉下来。
实际上是求掉下来的那一个-1即可。

我的想法是用一个parent[i]表示第i个节点的父节点，即挂在哪个节点上。

每次多挂一个就把它的所有祖先节点的载重增加，同时与最大载重量比较。

代码：

#include <iostream> #include <algorithm> #include <map> #include <vector> using namespace std; typedef long long ll; #define INF 2147483647int parent[50010];struct node{int c,w,p; }a[50010];int main(){int n;cin >> n;fill(parent,parent + n, -2);//父节点的索引号 for(int i = 0;i < n; i++) cin >> a[i].c >> a[i].w >> a[i].p,parent[i] = a[i].p;for(int i = 0;i < n; i++){parent[i] = a[i].p;//从i一直往上找，顺便比较 ，如果超重直接输出并return 0； int t = i;while(parent[t] != -1){a[parent[t]].w += a[i].w;if(a[parent[t]].c < a[parent[t]].w){cout << i << endl;return 0;}t = parent[t];}}//所有的都能挂上，输出n。 cout << n <<endl;return 0; }

总结

以上是生活随笔为你收集整理的51nod 1307 绳子与重物 （标记父节点更新即可）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。