题意: 加边是所有点连通，没有重边和自环,问最小代价
加边规则：两点权值奇偶性相同代价为a,否则为b
− 100 ≤ a , b ≤ 100 -100\leq a,b \leq100 −100≤a,b≤100
分析：
这题就是一个分类讨论,先读进来统计奇数点和偶数点
记 n a na na为奇偶性相同的点的连边， n b nb nb为奇偶性不同的点的连边, j i ji ji为奇数点, o u ou ou为偶数点
1. a ≤ 0 1.a\leq 0 1.a≤0 and b ≤ 0 : b\leq0: b≤0:
所有可以连的边都连上
n a = C ( 2 j i ) + C ( 2 o u ) na=C\binom{2}{ji}+C\binom{2}{ou} na=C(ji2)+C(ou2)
n b = j i ∗ o u nb=ji*ou nb=ji∗ou
2. a ≤ 0 2.a\leq 0 2.a≤0 and b > 0 : b>0: b>0:
n a = C ( 2 j i ) + C ( 2 o u ) na=C\binom{2}{ji}+C\binom{2}{ou} na=C(ji2)+C(ou2)
如果全是技术点或者偶数点，则不需要奇数点和偶数点连一条边
i f ( m i n ( j i , o u ) ) n b = 1 ; if(min(ji,ou)) nb = 1; if(min(ji,ou))nb=1;
3. a > 0 3.a> 0 3.a>0 and b ≤ 0 : b\leq0: b≤0:
如果既有奇数点又有偶数点，则它们之间的所有边都要，否则我只要n-1条边因为代价大于0
i f ( m i n ( j i , o u ) ) if(min(ji,ou)) if(min(ji,ou)) n b = j i ∗ o u ; nb = ji*ou; nb=ji∗ou;
e l s e else else n a = n − 1 ; na = n-1; na=n−1;
4. a > 0 4.a> 0 4.a>0 and b > 0 : b>0: b>0:
如果全是奇数或者偶数点，只取n-1条边即可
否则:
如果a<=b: n a = n − 2 ; na = n-2; na=n−2; n b = 1 nb = 1 nb=1
如果a>b: n b = n − 1 nb = n-1 nb=n−1即可
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i128 = __int128;
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n,a,b;
void solve(){
cin>>n>>a>>b;
long long ji = 0,ou = 0;
for(int i = 1;i<=n;++i){
int x;cin>>x;
ji+=(x%2==1);
ou+=(x%2==0);
}
long long na = 0,nb =0;
if(a<=0&&b<=0){
na = ji*(ji-1)/2+ou*(ou-1)/2;
nb = ji*ou;
}else if(a<=0){
na = (ji-1)*ji/2+ou*(ou-1)/2;
if(min(ji,ou)) nb = 1;
}else if(b<=0){
if(min(ji,ou)) nb = ji*ou;
else na = n-1;
}else{
if(min(ji,ou)==0){
na = n-1;
}else{
if(a<=b){
na = n-2;
nb = 1;
}else nb = n-1;
}
}
cout<<na*a+nb*b<<"\n";
}
int main(){
ios;
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
没开long long WA了好几发
