题目在这里
题意: 加边是所有点连通，没有重边和自环,问最小代价
加边规则：两点权值奇偶性相同代价为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了好几发
