## 2019 ACM/ICPC Asia Regional shanxia D Miku

2020-10-31 08:41发布

Miku is matchless in the world!” As everyone knows, Nakano Miku is interested in Japanese generals, so Fuutaro always plays a kind of card game about generals with her. In this game, the players pick up cards with generals, but some generals have contradictions and cannot be in the same side. Every general has a certain value of attack power (can be exactly divided by 100

This day Miku wants to play this game again. However, Fuutaro is busy preparing an exam, so he decides to secretly control the game and decide each card's owner. He wants Miku to win this game so he won't always be bothered, and the difference between their value should be as small as possible. To make Miku happy, if they have the same sum of values, Miku will win. He must get a plan immediately and calculate it to meet the above requirements, how much attack value will Miku have?

As we all know, when Miku shows her loveliness, Fuutaro's IQ will become 0

### Input

Each test file contains several test cases. In each test file:

The first line contains a single integer T(1 \le T \le 10)

For each test case, the first line contains two integers: the number of generals N(2 \le N \le 200)

The second line contains N

The following M

The input data guarantees that the solution exists.

### Output

For each test case, you should print one line with your answer.

### Hint

In sample test case, Miku will get general 2

#### 样例输入

1
4 2
1400 700 2100 900
1 3
3 4

#### 样例输出

2800

#include<bits/stdc++.h>
#define maxn 100005
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll n,m;
ll a[maxn],b[maxn];
vector<int> mp[maxn];
ll s,dp[maxn];
int vis[maxn];
void dfs(int x,int num){
vis[x]=s+num;
for(int i=0;i<mp[x].size();i++){
if(vis[mp[x][i]]==0){
if(num==0){
dfs(mp[x][i],1);
}
else{
dfs(mp[x][i],0);
}
}
}
}
int main(){
int t;
scanf("%d",&t);
while(t--){
for(int i=0;i<maxn;i++) mp[i].clear();
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
a[i]/=100;
}
int x,y;
for(int i=0;i<m;i++){
scanf("%d%d",&x,&y);
mp[x].push_back(y);
mp[y].push_back(x);
}
s=1;
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
if(vis[i]==0){
dfs(i,0);
s+=2;
}
}
s--;
ll sum=0,num=0;
memset(b,0,sizeof(b));
for(int i=1;i<=n;i++){
b[vis[i]]+=a[i];
sum+=a[i];
}
int q=1;

for(int i=1;i<=s;i+=2){
num+=min(b[i],b[i+1]);
b[q++]=abs(b[i]-b[i+1]);
}
ll z=sum/2+sum%2;
z-=num;
memset(dp,0,sizeof(dp));
for(int i=1;i<q;i++){
for(int j=z;j>=b[i];j--){
dp[j]=max(dp[j],dp[j-b[i]]+b[i]);
}
}
ll z1=num;
if(dp[z] != -1) z1+=dp[z];
ll z2=sum-z1;
printf("%lld\n",max(z1,z2)*100);
}
}
/*
1
4 2
1400 700 2100 900
1 3
3 4
*/

Ta的文章 更多文章

0条评论