7 solutions

  • 7
    @ 3 years ago 
    #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
 */
    Copy
    • 1
      @ 3 years ago 
      #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);
}
      Copy
      • 1
        @ 3 years ago

        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;
}
        Copy
        • 1
          @ 3 years ago

          题目来源

          2021年蓝桥省赛第二场E题

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

          视频讲解

          视频连接：

          https://www.bilibili.com/video/BV1pT4y12721/

          思路

          我们可以单独写一个计算边权的函数，然后将2021×2020/2×22021 \times 2020 / 2 \times 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
          Copy
          • 0
            @ 2 years ago

            看大家发的都是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;
}
            Copy
            • 0
              @ 2 years ago

              时隔这么多天，终于把这道题做了（泪目）

              #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;
}
              Copy
              • 0
                @ 3 years ago

                我是蒟蒻

                #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;
}
                Copy
                • 1

                E.城邦

                Information

                ID
                108
                Time
                1000ms
                Memory
                256MiB
                Difficulty
                6
                Tags
                # Submissions
                139
                Accepted
                43
                Uploaded By
                1. About
                2. Contact Us
                3. Privacy
                4. Terms of Service
                5. Copyright Complaint
                6. Language
                7. Legacy mode
                8. Theme
                2. 蜀ICP备2021003932号-1
                3. Worker 0, 65ms
                4. Powered by Hydro v4.19.1 Community