先预处理出有多少个任务即可
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int maxn = ;
const int maxm = ;
struct Edge{
int u,v,next;
}edge[ maxm ];
int cnt ,head[ maxn ];
void init(){
cnt = ;
memset( head,-,sizeof( head ) );
}
void addedge( int a,int b ){
edge[ cnt ].u = a;
edge[ cnt ].v = b;
edge[ cnt ].next = head[ a ];
head[ a ] = cnt ++;
}
int fa[ maxn ],root[ maxn ],dp[ maxn ];
int val[ maxn ],cost[ maxn ];
int find( int x ){
if( x==fa[x] ) return x;
else return fa[x] = find( fa[x] );
}
int main(){
int n,Max,k;
while( ~scanf("%d%d%d",&n,&Max,&k) ){
for( int i=;i<=n;i++ ){
scanf("%d%d",&val[i],&cost[i]);
fa[ i ] = i;
}
init();
memset( dp,,sizeof( dp ) );
memset( root,,sizeof( root ) );
while( k-- ){
int a,b;
scanf("%d%d",&a,&b);
int x = find(a);
int y = find(b);
if( fa[x]!=y ){
fa[x] = y;
}
}
int r = ;
for( int i=;i<=n;i++ ){
int x = find( i );
if( root[x]== ){
root[x] = r++;
}
addedge( root[x],i );
}
for( int i=;i<r;i++ ){
for( int j=Max;j>=;j-- ){
for( int k=head[i];k!=-;k=edge[k].next ){
int nxt = edge[k].v;
if( j>=cost[nxt] ){
dp[j] = max( dp[j],dp[j-cost[nxt]]+val[nxt] );
}
}
}
}
printf("%d\n",dp[Max]);
}
return ;
}