网易4.16笔试通用技术第三题
大概题意就是给几个点几个边问删除边获得的最大权值数
权值计算方法是两个点的权值相乘后数字末尾0的个数
其实就是一个求最小生成树的题,求删边的最大权值就是求生成一个最小权值的树,kruskal算法即可
笔试服务器崩了不知道此题ac情况,但是我觉得此题***不离十是这么写的
#include<bits/stdc++.h>
using namespace std;
class unionSet{
public:
int *fa, n;
unionSet(int n) : n(n){
fa = new int[n + 1];
for(int i = 0; i <= n; i++) fa[i] = i;
}
int find(int x) {return fa[x] = (fa[x] == x ? x : find(fa[x]));}
void merge(int a, int b){fa[find(a)] = find(b);}
};
struct edge{
int s, e, v;
};
bool cmp(const edge& a, const edge& b){
return a.v < b.v;
}
edge edg[200005];
int n, m, cnt, edg_cnt, num[200005], res, sum;
void add_edge(int s, int e){
int ret = 0;
edg[edg_cnt].s = s;
edg[edg_cnt].e = e;
int t = num[s] * num[e];
string str = to_string(t);
for(auto x : str) {
if(x == '0') ret++;
}
edg[edg_cnt].v = ret;
sum += ret;
edg_cnt++;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> num[i];
}
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
add_edge(a, b);
}
sort(edg, edg + m, cmp);
unionSet u(n);
for(int i = 0; i < m; i++){
int s = edg[i].s, e = edg[i].e, v = edg[i].v;
if(u.find(s) != u.find(e)){
u.merge(s, e);
res += v;
cnt++;
if(cnt == n - 1){
cout << sum - res << endl;
return 0;
}
}
}
cout << "orz" << endl;
return 0;
} #网易笔试##实习##春招##笔试题目#
字节跳动公司氛围 553人发布
