Information
- ID
- 1264
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- 10
- Tags
- # Submissions
- 3
- Accepted
- 1
- Uploaded By
#include<bits/stdc++.h>
using namespace std;
#define ioio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#define debug(x) cout<<#x<<":"<<x<<endl;
#define L(k) k<<1
#define R(k) k<<1|1
#define P pair
#define P1 first
#define P2 second
#define u_map unordered_map
#define p_queue priority_queue
typedef long long ll;
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int INF2 = (1 << 31);
const int N = 1e6 + 7;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
/*-------------------------------------------------*/
int n,m,w;
struct st{
int c,d;
}pre[N];
int dp[N];
vector<st>V;
int fa[N];
void init(int n){
for(int i=1;i<=n;i++)
fa[i]=i;
}
int fin(int x){
if(x!=fa[x])
fa[x]=fin(fa[x]);
return fa[x];
}
void mer(int x,int y){
x=fin(x),y=fin(y);
fa[x]=y;
}
int main(){
ioio
cin>>n>>m>>w;
init(n);
int c,d;
for(int i=1;i<=n;i++){
cin>>c>>d;
pre[i].c=c,pre[i].d=d;
}
int u,v;
while(m--){
cin>>u>>v;
mer(u,v);
}
for(int i=1;i<=n;i++)
if(i!=fa[i]){
int f=fin(i);
pre[f].c+=pre[i].c;
pre[f].d+=pre[i].d;
}
for(int i=1;i<=n;i++)
if(i==fa[i])
V.push_back({pre[i].c,pre[i].d});
cout<<endl;
int len=V.size();
for(int i=1;i<=len;i++)
for(int j=w;j>=V[i-1].c;j--)
dp[j]=max(dp[j],dp[j-V[i-1].c]+V[i-1].d);
cout<<dp[w]<<endl;
return 0;
}
By signing up a 追梦算法网 universal account, you can submit code and join discussions in all online judging services provided by us.