1 条题解
-
0
#include <bits/stdc++.h> using namespace std; int n,m,w; struct stu{ int c,d; }crr[100100]; int arr[200100];//arr-存放父亲结点 int brr[200100];//brr-记录当前层数,用于优化 struct stn{ int c,d; }; struct stn drr[200100]={}; int dp[200100]={}; int find(int x){//寻找当前位置的父亲结点 if(arr[x]==x)//如果当前的人指向自己 return x; else return find(arr[x]);//向上寻找父亲结点 } void unite(int a,int b){ a=find(a);//寻找a的父亲结点 b=find(b);//寻找b的父亲结点 if(a==b) return;//a和b是同一个父亲结点 //低层次向高层次合并 if(brr[a] < brr[b]){ arr[a]=b; }else if(brr[a] > brr[b]){ arr[b]=a; }else{ arr[b]=a; brr[a]++;//a的层数+a,把b合并到a } } int main() { cin>>n>>m>>w; for(int i=1;i<=n;i++) cin>>crr[i].c>>crr[i].d; //1.初始化 for(int i=1;i<=n;i++){ arr[i]=i;//每个人是自己的父亲结点 brr[i]=1;//每个结点一开始只有一个人 } int a,b; for(int i=1;i<=m;i++){ cin>>a>>b; //把a能连接人与b能连接人想连接 unite(a,b); } //把所有的数据都加到根节点去 for(int i=1;i<=n;i++){ int a=find(i);//寻找根节点 drr[a].c+=crr[i].c; drr[a].d+=crr[i].d; } for(int i=1;i<=n;i++){ int a=find(i);//寻找根节点 drr[i].c=drr[a].c; drr[i].d=drr[a].d; } dp[0]=0; for(int i=1;i<=n;i++){ for(int j=w;j>=drr[i].c;j--){ dp[j]=max(dp[j],dp[j-drr[i].c]+drr[i].d); } } cout<<dp[w]; return 0; }
- 1
信息
- ID
- 1356
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者