题目链接:传送门
题目思路:并查集加分组背包
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <cstring> #include <stack> #include <cctype> #include <queue> #include <string> #include <vector> #include <set> #include <map> #include <climits> #define lson root<<1,l,mid #define rson root<<1|1,mid+1,r #define fi first #define se second #define seg int root,int l,int r #define ping(x,y) ((x-y)*(x-y)) #define mst(x,y) memset(x,y,sizeof(x)) #define mcp(x,y) memcpy(x,y,sizeof(y)) #define Min(x,y) (x<y?x:y) #define Max(x,y) (x>y?x:y) using namespace std; #define gamma 0.5772156649015328606065120 #define MOD 1000000007 #define inf 0x3f3f3f3f #define N 200001 #define maxn 1021 typedef long long LL; typedef pair<int,int> PII; vector<int>V[1001]; int fp[1001],n,m,k; int c[1001],v[1001]; int dp[1001]; int findp(int x){return fp[x]==x?x:fp[x]=findp(fp[x]);} int main(){ // freopen("lxx.txt","r",stdin); int i,j,group,x,y,Case=0; while(scanf("%d%d%d",&n,&k,&m)!=EOF){ for(i=1;i<=n;++i) fp[i]=i; mst(dp,0); for(i=1;i<=n;++i){scanf("%d%d",&v[i],&c[i]);V[i].clear();} while(m--){ scanf("%d%d",&x,&y); int t1=findp(fp[x]); int t2=findp(fp[y]); if(t1!=t2) fp[t1]=t2; } for(i=1;i<=n;++i){ int t1=findp(i); V[t1].push_back(i); } for(i=1;i<=n;++i) if(V[i].size()) for(j=k;j>=0;--j) for(int l=0;l<V[i].size();++l){ int t=V[i][l]; if(c[t]<=j) dp[j]=Max(dp[j],dp[j-c[t]]+v[t]); } printf("%d ",dp[k]); } return 0; }