数据结构_并查集(不是带权的，误判了)-白红宇

数据结构_并查集(不是带权的，误判了)

阅读量：259 次

发布时间：2019-03-01

本文共 1765 字，大约阅读时间需要 5 分钟。

题意：

1307 绳子与重物

1.0 秒 131,072.0 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。

输入

第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 2 -1

3 3 0

6 1 -1

3 1 0

3 2 3

输出样例

思路：

认真读题啊！！！

“给出每条绳子的负重Ci、重物的重量Wi以及绳子会挂在之前的哪条绳子的下面，问最多挂多少个绳子而不会出现绳子断掉的情况。”

第i条绳子都是挂在之前的绳子的下面的

所以可以并查集写。。。可以从前往后挂，也就是依次**把儿子挂到父节点（把第i条绳子挂在1 ~ i - 1的某一条绳子）上，然后返回到父节点，以及父节点的父节点。。是个回溯(最后回到-1，肯定都是要挂在钩子上的嘛)**的过程。。。判断挂这条绳子会不会使某条绳子断掉，断掉就输出当前绳子的编号，然后return 0 （感觉时间复杂度会高）

也可以从后往前挂，如果绳子要断掉了。。就从最后开始删除儿子节点（）。。看看最后有多少条绳子是挂上去的（return res），就是答案了

代码实现：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               using namespace std;typedef long long ll;const int maxn = 2e5 + 5;int pre[maxn];int sum[maxn];int c[maxn],w[maxn],p[maxn];int n;int find(int x){ if(x == pre[x]) return x; else return pre[x] = find(pre[x]);}int solve(){ int res = n; //给出每条绳子的负重Ci、重物的重量Wi以及绳子会挂在之前的哪条绳子的下面,所以要倒着找，倒着删。。。 for(int i = n;i >= 1;i--){ while(sum[i] > c[i]){ int fa = find(res); sum[fa] -= w[res]; res--; } sum[p[i]] += sum[i]; pre[i] = p[i]; } return res;}int main(){ scanf("%d",&n); for(int i = 1;i <= n;i++) pre[i] = i; memset(c,0,sizeof(c)); memset(w,0,sizeof(w)); memset(p,0,sizeof(p)); memset(sum,0,sizeof(sum)); for(int i = 1;i <= n;i++){ scanf("%d%d%d",&c[i],&w[i],&p[i]); sum[i] += w[i]; p[i]++; } int ans = solve(); printf("%d\n",ans); return 0;}

转载地址：http://jpox.baihongyu.com/

你可能感兴趣的文章

mysql中json_extract的使用方法

mysql中null和空字符串的区别与问题！

查看>>