比较简单的题
并查集维护一下必须选择的大小 也就是物品
然后0/1背包处理指定体积能否组成
(一开始开bool想做一个传递真值就是D不出来....能有dalao讲一下吗)
Code:
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<queue> 5 #define ms(a,b) memset(a,b,sizeof a) 6 #define rep(i,a,n) for(int i = a;i <= n;i++) 7 #define per(i,n,a) for(int i = n;i >= a;i--) 8 #define inf 1000000007 9 using namespace std; 10 typedef long long ll; 11 typedef double D; 12 #define eps 1e-8 13 ll read() { 14 ll as = 0,fu = 1; 15 char c = getchar(); 16 while(c < '0' || c > '9') { 17 if(c == '-') fu = -1; 18 c = getchar(); 19 } 20 while(c >= '0' && c <= '9') { 21 as = as * 10 + c - '0'; 22 c = getchar(); 23 } 24 return as * fu; 25 } 26 //head 27 const int N = 100005; 28 int n,m,k; 29 30 int pa[N],d[N]; 31 int gpa(int x) { 32 if(pa[x] == x) return x; 33 return pa[x] = gpa(pa[x]); 34 } 35 int Merge(int x,int y) { 36 int fx = gpa(x),fy = gpa(y); 37 if(fx ^ fy) pa[fx] = fy,d[fy] += d[fx]; 38 } 39 40 int stk[N],top; 41 int dp[N<<1]; 42 #define Abs(x) (((x)>(~(x)+1)) ? x : (~(x)+1)) 43 int main() { 44 // freopen("in.in","r",stdin); 45 n = read(),m = read(),k = read(); 46 rep(i,1,n) pa[i] = i,d[i] = 1; 47 rep(i,1,k) Merge(read(),read()); 48 rep(i,1,n) if(pa[i] == i) stk[++top] = d[i]; 49 rep(i,1,top) { 50 per(j,m<<1,stk[i]) { 51 dp[j] = max(dp[j],dp[j-stk[i]] + stk[i]); 52 } 53 } 54 int ans = inf,minn = inf; 55 rep(i,1,m<<1) { 56 if(minn > Abs(dp[i]-m)) minn = Abs(dp[i]-m),ans = dp[i]; 57 } 58 printf("%d ",ans == inf ? 0 : ans); 59 return 0; 60 }