本文主要是介绍2024/2/28 最小生成树 kruskal +cf div3 （929），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
买礼物
买礼物 - 洛谷
CF div3 929 A题
Problem - A - Codeforces
CF div3 929 B题
Problem - B - Codeforces
买礼物
买礼物 - 洛谷
思路：kruskal算法，有优惠就建边
完整代码：
#include <bits/stdc++.h>
#define int long long
#define PII std::pair<int,int>
const int N = 1010;
int p[N];
int find(int x)
{if(p[x]!=x) p[x]=find(p[x]);return p[x];
}
signed main()
{int a,b;int c=0,ans=0;std::cin >> a >> b;std::vector<std::pair<int,std::pair<int,int>>> g;for(int i = 1;i <= b;i ++){p[i]=i;}for(int i = 1;i <= b;i ++){for(int j = 1;j <= b;j ++){int x;std::cin >> x;if(i>=j||x==0)continue;else {int aa=std::min(x,a);g.push_back({aa, {i, j}});}}}std::sort(g.begin(),g.end());for(auto it: g){int f1 = find(it.second.first);int f2 = find(it.second.second);if (f1 != f2) {p[f1] = f2;c++;ans += it.first;}}if(c+1==b) {ans += a;std::cout << ans;}else{std::cout<<ans+(b-c)*a;}return 0;
}CF div3 929 A题
Problem - A - Codeforces
思路：每个数的绝对值的和
完整代码：
#include <bits/stdc++.h>
#define int long long
#define PII std::pair<int,int>
const int N = 110;
signed main()
{int t;std::cin >> t;while(t --) {int n;std::cin >> n;int ans = 0;std::vector<int> a;for (int i = 0; i < n; i++) {int x;std::cin >> x;if (x < 0)x = -x;ans += x;}std::cout << ans<<"\n";}return 0;
}CF div3 929 B题
Problem - B - Codeforces
思路：
分类讨论
1.如果sum%3==0 此时是3的倍数，输出答案0
2.如果sum%3==2 此时不管是删去一个数还是加上1都能构成3的倍数，所以输出答案1
3.如果sum%3==1
此时如果有一个数%3==1，那删去这个数就可以了，输出答案1
如果没有任何一个数%3==1，那就要加上两个1或者删去两个数，输出答案2
完整代
#include <bits/stdc++.h>
#define int long long
#define PII std::pair<int,int>
const int N = 2e5+10;
signed main()
{int t;std::cin >> t;while(t --){int n;std::cin >> n;std::vector<int> a(n+1);int sum=0;int flag=0;for(int i = 1;i <= n;i ++){std::cin >> a[i];if(a[i]%3==1){flag=1;}sum+=a[i];}if(sum%3==0)std::cout<<0<<"\n";else if(sum%3==2)std::cout<<1<<"\n";else if(sum%3==1){if(flag==1)std::cout<<1<<"\n";elsestd::cout<<2<<"\n";}}return 0;
}码：
这篇关于2024/2/28 最小生成树 kruskal +cf div3 （929）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
