本文主要是介绍牛客小白月赛96 D 最小连通代价，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目在这里
题意: 加边是所有点连通，没有重边和自环,问最小代价
加边规则：两点权值奇偶性相同代价为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了好几发
这篇关于牛客小白月赛96 D 最小连通代价的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
