Komprise -1
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687
#include <bits/stdc++.h>
using namespace std;
pair<int,int> dfs(int s, vector<int> &visited, vector<vector<int>> adj, vector<vector<int>> employee){
visited[s] = true;
int a1 = 0;
int a2 = 0;
a1 += employee[s][1];
a2 += employee[s][0];
for(auto i: adj[s]){
if(visited[i] == false){
pair<int,int> t = dfs(i,visited,adj,employee);
a1 += t.first;
a2 += t.second;
}
}
return {a1,a2};
}
int helper(vector<pair<int,int>> groups, int bu){
vector<vector<int>> dp(groups.size()+1, vector<int>(bu+1));
for(int i=0; i<groups.size()+1; i++){
for(int j=0; j<bu+1; j++){
if(i == 0 || j == 0){
dp[i][j] = 0;
}else{
if(groups[i-1].first <= j){
dp[i][j] = max(dp[i-1][j], dp[i-1][j-groups[i-1].first] + groups[i-1].second);
}else{
dp[i][j] = dp[i-1][j];
}
}
}
}
return dp[groups.size()][bu];
}
int main() {
int n;cin>>n;
vector<vector<int>> employee(n,vector<int>(2));
for(int i=0; i<employee.size(); i++){
cin>>employee[i][0];
cin>>employee[i][1];
}
int q;cin>>q;
vector<vector<int>> adj(n);
for(int i=0; i<q; i++){
int a; cin>>a;
int b; cin>>b;
adj[a-1].push_back(b-1);
adj[b-1].push_back(a-1);
}
int bu; cin>>bu;
vector<pair<int,int>> groups;
vector<int> visited(n);
for(int i=0; i<n; i++){
if(visited[i] == false){
pair<int,int> t = dfs(i,visited,adj, employee);
groups.push_back(t);
}
}
// for(int i=0; i<groups.size(); i++){
// cout<<groups[i].first<<" "<<groups[i].second<<endl;
// }
int maxSkills = helper(groups, bu);
cout<<maxSkills;
return 0;
}
Cpp
INFO