首页 > 代码库 > 51nod 1307：绳子与重物
51nod 1307：绳子与重物
51nod 1307：绳子与重物
题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1307
题目大意：给定$n$条绳子，每条绳子有最大承重$C_i$，总量$W_i$和挂点$P_i$，问按顺序挂最多挂几条绳子.
并查集
考虑逆序挂绳子，若当前绳子最大承重小于实际承重，则将后面的绳子删去.复杂度$O(n)$.
代码如下：
1 #include <cstdio> 2 #include <iostream> 3 using namespace std; 4 int n,l,pre[50005],tot[50005],w[50005]; 5 struct node{ 6 int maxw,w,p,id; 7 }a[50005]; 8 void init(){ 9 for(int i=0;i<=50000;++i)10 pre[i]=i;11 }12 int Find(int x){13 return x==pre[x]?x:pre[x]=Find(pre[x]);14 }15 void Union(int a,int b){16 int x=Find(a),y=Find(b);17 if(x!=y)pre[x]=y;18 }19 int main(void){20 init();21 scanf("%d",&n);22 for(int i=n-1;i>=0;--i){23 scanf("%d%d%d",&a[i].maxw,&a[i].w,&a[i].p);24 a[i].id=n-1-i;25 }26 for(int i=0;i<n;++i){27 int x=a[i].id,p=a[i].p;28 tot[x]=a[i].maxw;29 w[x]+=a[i].w;30 while(tot[x]<w[x]&&l<=i){31 w[Find(a[l].id)]-=a[l].w;32 l++;33 }34 if(p!=-1){35 Union(x,p);36 w[p]+=w[x];37 }38 }39 printf("%d\n",n-l);40 }
51nod 1307：绳子与重物
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。