7 solutions
-
6
#include <iostream> #include <algorithm> using namespace std; int main() { cout << 4046<< endl; return 0; } /** * ii. ;9ABH, * SA391, .r9GG35&G * &#ii13Gh; i3X31i;:,rB1 * iMs,:,i5895, .5G91:,:;:s1:8A * 33::::,,;5G5, ,58Si,,:::,sHX;iH1 * Sr.,:;rs13BBX35hh11511h5Shhh5S3GAXS:.,,::,,1AG3i,GG * .G51S511sr;;iiiishS8G89Shsrrsh59S;.,,,,,..5A85Si,h8 * :SB9s:,............................,,,.,,,SASh53h,1G. * .r18S;..,,,,,,,,,,,,,,,,,,,,,,,,,,,,,....,,.1H315199,rX, * ;S89s,..,,,,,,,,,,,,,,,,,,,,,,,....,,.......,,,;r1ShS8,;Xi * i55s:.........,,,,,,,,,,,,,,,,.,,,......,.....,,....r9&5.:X1 * 59;.....,. .,,,,,,,,,,,... .............,..:1;.:&s * s8,..;53S5S3s. .,,,,,,,.,.. i15S5h1:.........,,,..,,:99 * 93.:39s:rSGB@A; ..,,,,..... .SG3hhh9G&BGi..,,,,,,,,,,,,.,83 * G5.G8 9#@@@@@X. .,,,,,,..... iA9,.S&B###@@Mr...,,,,,,,,..,.;Xh * Gs.X8 S@@@@@@@B:..,,,,,,,,,,. rA1 ,A@@@@@@@@@H:........,,,,,,.iX: * ;9. ,8A#@@@@@@#5,.,,,,,,,,,... 9A. 8@@@@@@@@@@M; ....,,,,,,,,S8 * X3 iS8XAHH8s.,,,,,,,,,,...,..58hH@@@@@@@@@Hs ...,,,,,,,:Gs * r8, ,,,...,,,,,,,,,,..... ,h8XABMMHX3r. .,,,,,,,.rX: * :9, . .:,..,:;;;::,.,,,,,.. .,,. ..,,,,,,.59 * .Si ,:.i8HBMMMMMB&5,.... . .,,,,,.sMr * SS :: h@@@@@@@@@@#; . ... . ..,,,,iM5 * 91 . ;:.,1&@@@@@@MXs. . .,,:,:&S * hS .... .:;,,,i3MMS1;..,..... . . ... ..,:,.99 * ,8; ..... .,:,..,8Ms:;,,,... .,::.83 * s&: .... .sS553B@@HX3s;,. .,;13h. .:::&1 * SXr . ...;s3G99XA&X88Shss11155hi. ,;:h&, * iH8: . .. ,;iiii;,::,,,,,. .;irHA * ,8X5; . ....... ,;iihS8Gi * 1831, .,;irrrrrs&@ * ;5A8r. .:;iiiiirrss1H * :X@H3s....... .,:;iii;iiiiirsrh * r#h:;,...,,.. .,,:;;;;;:::,... .:;;;;;;iiiirrss1 * ,M8 ..,....,.....,,::::::,,... . .,;;;iiiiiirss11h * 8B;.,,,,,,,.,..... . .. .:;;;;iirrsss111h * i@5,:::,,,,,,,,.... . . .:::;;;;;irrrss111111 * 9Bi,:,,,,...... ..r91;;;;;iirrsss1ss1111 */ -
1
#include<stdio.h> #include<stdlib.h> /*图的最小生成树问题 任意两个城邦之间都有桥直接连接，则构成了图 现要装饰其中的一部分桥要保证从一个城邦到另 一个城邦之间可以完全只通过装饰的桥到达，那么 根据题意至少要2020座桥，并且要保证开支最少， 这就是典型的最小生成树问题，任意城邦之间的桥 上面是有权值的也就是桥的开销，我们通过排序依照权值 从小到大的顺序依次装饰桥，注意不能有回路否则就不能保证 从一个城邦到另一个城邦可以完全只通过装饰桥到达了 */ typedef struct tu{ //head和tail分别表示桥两边的结点 int head; int tail; int value;//表示权值 }Tu; Tu array[10000007]; int f[2027]; int cnt = 0; int count = 0; int comp(const void *a, const void *b){ //将void指针类型强制转化为结构体指针类型 Tu *c = (Tu *)a; Tu *d = (Tu *)b; return c->value-d->value; } //寻找每一个结点的根结点 int find(int x){ if(x == f[x])//如果某个结点的根结点就是他本身说明这个结点还没有连通 return x; else{ f[x] = find(f[x]);//递归调用找到f[x]的最终的根结点也就是祖先结点 return f[x];//返回f[x]的祖先结点 } } //主要是防止树种生成环 int merge(int x, int y){ int t1,t2; //找到两个结点的祖先结点判断是否在一个集合中也就是说是否有公共的祖先结点 t1 = find(x); t2 = find(y); //如果两个结点的祖先结点不等则可以进行连接 if(t1 != t2){ f[t2] = t1;//根据靠左原则t2的父节点设为t1 return 1; } return 0; } //求桥的权值 void add(int x,int y){ int a,b; int sum = 0;//每座桥的sum都可能不同因此一定要每次调用时都设为0 cnt++; array[cnt].head = x; array[cnt].tail = y; while(x!=0 || y!=0){ a = x%10; b = y%10; if(a != b){ sum += a+b; } x /= 10; y /= 10; } array[cnt].value = sum; return; } int main(){ int sum = 0; for(int i=1; i<=2021; i++) f[i] = i;//初始时每个结点的根结点就是结点本身 //列举所有桥之间连接的可能 for(int i=1; i<=2021; i++){ for(int j=i+1; j<=2021; j++){ add(i,j); } } qsort(array+1,cnt,sizeof(array[0]),comp); for(int i=1; i<=cnt; i++){ if(merge(array[i].head,array[i].tail)){ count++; sum += array[i].value; } if(count == 2020) break; } printf("%d\n",sum); } -
1
kruskal（克鲁斯卡尔）算法，模板题，直接往上套就完了
#include<bits/stdc++.h> using namespace std; int f[2027],cnt; struct edge{ int start,end,val; }e[10000007]; int cmp(edge a,edge b){ return a.val<b.val; } int find(int x){ if(x==f[x]) return x; return f[x]=find(f[x]); } int ff(int x,int y){ int sum=0; while(x!=0||y!=0){ int xx=x%10,yy=y%10; if(xx!=yy) sum+=xx+yy; x/=10,y/=10; } return sum; } void add(int x,int y){ e[++cnt].start=x; e[cnt].end=y; e[cnt].val=ff(x,y); } int sum=0,total; void kruskal(){ for(int i=1;i<=cnt;i++){ int xx=find(e[i].start),yy=find(e[i].end); if(xx==yy) continue; sum+=e[i].val; f[xx]=yy; total++; if(total==2020) break; } } int main(){ for(int i=1;i<=2021;i++) f[i]=i; for(int i=1;i<=2021;i++){ for(int j=i+1;j<=2021;j++){ add(i,j); } } sort(e+1,e+cnt+1,cmp); kruskal(); printf("%d",sum); return 0; } -
1
题目来源
2021年蓝桥省赛第二场E题
http://acm.mangata.ltd/p/P1104
视频讲解
视频连接：
https://www.bilibili.com/video/BV1pT4y12721/
思路
我们可以单独写一个计算边权的函数，然后将条边放进我们的数组或者容器里面，然后一一判断即可，然后跑一个最小生成树即可，关于计算边权的方法请参考下面的
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 -
0
看大家发的都是kruskal算法的，那我发个prim算法的吧，我觉得prim算法适合这道题这种稠密图的情况
#include<iostream> #include<cstring> #include<algorithm> using namespace std; #define inf 0x3f3f3f3f #define v_n 2021 int w_m[2021][2021]; int sideWeight(int x,int y) { int sum_w=0; while(x!=0||y!=0) { if(x%10!=y%10)//a和b相同位数下的数字不同 { sum_w+=x%10; sum_w+=y%10; } x/=10; y/=10; } return sum_w; } int prim() { bool is_visited[v_n]={0}; int dis[v_n],sum_w=0; for(int i=0;i<v_n;++i) { dis[i]=w_m[0][i]; } is_visited[0]=1; for(int i=0;i<v_n-1;++i) { int min_w=inf,min_v=-1; for(int j=0;j<v_n;++j) { if(is_visited[j]==0&&dis[j]<min_w)//prim算法的核心是每次从没添加到生成树的节点中寻找到生成树最近的节点添加到生成树中 { min_w=dis[j]; min_v=j; } } for(int j=0;j<v_n;++j) { dis[j]=min(dis[j],w_m[min_v][j]); } is_visited[min_v]=1; sum_w+=min_w; } return sum_w; } int main() { for(int i=0;i<v_n;++i) { for(int j=0;j<v_n;++j) { w_m[i][j]=sideWeight(i,j);//生成图的权值矩阵 } w_m[i][i]=0; } cout<<prim()<<endl; } -
0
时隔这么多天，终于把这道题做了（泪目）
#include<iostream> #include<algorithm> using namespace std; int t=1,f[2027]; struct Edge{ int u,v,w; }edges[4084441]; bool cmp(Edge a,Edge b){ return a.w<b.w; } int val_num(int x,int y){ int sum=0; while(x||y){ if(x%10!=y%10){ sum+=x%10; sum+=y%10; } x/=10; y/=10; } return sum; } int find(int x){ if(x==f[x])return x; else return find(f[x]); } void val(){ for(int i=1;i<=2021;i++){ for(int j=1;j<=2021;j++){ if(i==j)continue; edges[t].u=i; edges[t].v=j; edges[t].w=val_num(i,j); t++; } } } int kruskal(){ int total=0,sum=0; for(int i=1;i<=t;i++){ Edge e=edges[i]; int u=find(e.u),v=find(e.v),w=e.w; if(u==v)continue; total+=w; f[u]=v; sum++; if(sum==2020)break; } return total; } int main(){ val_num(1511,501); val(); for(int i=1;i<=2021;i++)f[i]=i; sort(edges+1,edges+t+1,cmp); cout<<kruskal(); return 0; } -
0
我是蒟蒻
#include<bits/stdc++.h> using namespace std; typedef long long ll; int fa[2031]; struct edge { int start,end,val; }; bool cmp(edge a,edge b) { return a.val<b.val; } vector<edge> V; int get(int a,int b) { int ans=0; vector<int> first,sec; while(a>0) { first.push_back(a%10); a/=10; } while(b>0) { sec.push_back(b%10); b/=10; } int lenth1=first.size(),lenth2=sec.size(); int i=0; while(i<lenth1&&i<lenth2) { if(first[i]!=sec[i]) ans+=first[i]+sec[i]; i++; } while(i<lenth1) ans+=first[i++]; while(i<lenth2) ans+=sec[i++]; return ans; } 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; } int kruskal() { int ans=0; for(int i=1;i<=2021;++i) { fa[i]=i; } int lenth=V.size(); for(int i=0;i<lenth;++i) { int s=V[i].start; int e=V[i].end; s=find(s); e=find(e); if(s!=e) { ans+=V[i].val; fa[e]=s; } } return ans; } int main() { for(int i=1;i<=2021;++i) { for(int j=i+1;j<=2021;++j) { int val=get(i,j); V.push_back({i,j,val}); } } sort(V.begin(),V.end(),cmp); cout<<kruskal()<<"\n"; return 0; }
- 1