题目来源

2021年蓝桥省赛第二场E题

http://acm.mangata.ltd/p/P1104

视频讲解

视频连接：https://www.bilibili.com/video/BV1pT4y12721/

思路

我们可以单独写一个计算边权的函数，然后将 2021 × 2020 / 2 × 2 2021 \times 2020 / 2 \times 2 2021×2020/2×2条边放进我们的数组或者容器里面，然后一一判断即可，然后跑一个最小生成树即可，关于计算边权的方法请参考下面的get函数

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000009
#define endl "\n"
#define PII pair<int,int>

const int N = 2e6+10;
int n = 2021;
int fa[2030];

void init(){
	for(int i = 1;i <= n; ++i) fa[i] = i;
}

int find(int x) {
	int t = x; 
	while(t != fa[t]) t = fa[t];
	while(x != fa[x]) {
		int temp = fa[x];
		fa[x] = t;
		x = temp;
	}
	return x;
}

struct Edge{
	int u,v,w;//起点，终点，权值
};
bool cmp(Edge a, Edge b){
	return a.w < b.w;
} 
vector<Edge> V;


int get(int a,int b) {
	int ans = 0;
	vector<int> l,r;
	while(a) {
		l.push_back(a%10);
		a/=10;
	}
	while(b){
		r.push_back(b%10);
		b/=10;
	}
	int len1 = l.size(),len2 = r.size();
	int i = 0;
	while(i < len1 && i < len2){
		if(l[i] != r[i]) ans += l[i] + r[i];
		i++;
	}
	while(i < len1) ans += l[i++];
	while(i < len2) ans += r[i++];
	return ans;
}



int kruskal(){
	int ans = 0;
	init();
	int m = V.size();
	for(int i = 0;i < m; ++i){
		int u = V[i].u,v = V[i].v;
		u = find(u);
		v = find(v);
		if(u != v) {
			ans += V[i].w;
			fa[v] = u;
		}
	}
	return ans;
}

int main()
{
	cout<<4046<<endl;
	return 0;
	for(int i = 1;i <= n; ++i) {
		for(int j = i + 1;j <= n; ++j) {
			int w = get(i,j);
			V.push_back({i,j,w});
			V.push_back({j,i,w});
		}
	}
	sort(V.begin(),V.end(),cmp);
	cout<<kruskal()<<endl;
	
	return 0;
}
//4046