【题目】
Miku and Generals
【代码】
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1000005; int a[maxn],f[maxn];; int dp[maxn],sum[maxn]; int pre[maxn],vis[maxn]; int l[maxn],r[maxn]; int Find(int x){return x==pre[x]?x:pre[x]=Find(pre[x]);} void join(int x,int y) { int fx=Find(x),fy=Find(y); if(fx!=fy) pre[fx]=fy; } int main() { int t; scanf("%d",&t); while(t--){ int qum=0; int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); a[i] /= 100; qum += a[i]; sum[i]=a[i]; pre[i]=i; vis[i]=0; } int x,y; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) vis[j]=Find(vis[Find(j)]); scanf("%d%d",&x,&y); if(vis[Find(x)]==0&&vis[Find(y)]==0) { vis[Find(y)]=x; vis[Find(x)]=y; } else if(Find(vis[Find(x)])==0) { sum[Find(vis[Find(y)])]+=sum[Find(x)]; join(Find(x),Find(vis[Find(y)])); vis[Find(x)]=Find(y); } else if(Find(vis[Find(y)])==0) { sum[Find(vis[Find(x)])]+=sum[Find(y)]; join(Find(y),Find(vis[Find(x)])); vis[Find(y)]=Find(x); } else if(Find(y)!=Find(vis[Find(x)])) { sum[Find(x)]+=sum[Find(vis[Find(y)])]; join(Find(vis[Find(y)]),Find(x)); sum[Find(y)]+=sum[Find(vis[Find(x)])]; join(Find(vis[Find(x)]),Find(y)); vis[Find(x)]=Find(y); vis[Find(y)]=Find(x); } } int q=0; for(int j=1;j<=n;j++) vis[j]=Find(vis[Find(j)]); for(int i=1;i<=n;i++) { if(sum[Find(i)]==0&&sum[Find(vis[Find(i)])]==0) continue; else if(vis[i]!=0){ q++; l[q]=sum[Find(i)],r[q]=sum[Find(vis[Find(i)])]; sum[Find(i)]=0,sum[Find(vis[Find(i)])]=0; } } int ssum=0; for(int i=1;i<=q;i++){ ssum+=min(l[i],r[i]); dp[i]=abs(l[i]-r[i]); } for(int i=1;i<=n;i++){ if(vis[i]==0) dp[++q]=a[i]; } memset(f,0,sizeof(f)); f[ssum]=1; for(int i=1;i<=q;++i) for(int j=qum/2;j>=dp[i];--j) if(f[j-dp[i]]) f[j] = 1; ll ans=0; for(int i=qum/2;i>=0;--i) if(f[i]){ ans=max(i*(ll)100,(qum-i)*(ll)100); break; } printf("%lld\n",ans); } return 0; }
