第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)。
输出1个数，最多挂到第几个绳子，不会出现绳子断掉的情况。
5 5 2 -1 3 3 0 6 1 -1 3 1 0 3 2 3
3
题目意思很明确了，就是绳子有最大载重，下面挂东西，问最多挂多少个不掉下来。
实际上是求掉下来的那一个-1即可。
我的想法是用一个parent[i]表示第i个节点的父节点，即挂在哪个节点上。
每次多挂一个就把它的所有祖先节点的载重增加，同时与最大载重量比较。
代码：
#include <iostream> #include <algorithm> #include <map> #include <vector> using namespace std; typedef long long ll; #define INF 2147483647 int 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; }
原文：http://www.cnblogs.com/zhangjiuding/p/7729865.html
