发表更新Problem Solutions2 分钟读完 (大约275个字)

题解：洛谷P8207 [THUPC2022 初赛] 最小公倍树

巩固一下最小生成树的Kruskal算法（）

洛谷

思路

首先如果我们将完全图的所有边都存下来，最多需要 $(R-L)^2$ 条边，时空复杂度皆到了 $10^{10}$

所以我们选择在存边的部分进行优化

首先对于两个点，它们连边的权值为 $lcm(u,v)$ ，这意味着当 $gcd(u,v)$ 越大，权值越优

因此，对于每一个 $i\in{[1,R]}$，我们枚举它符合在 $[L,R]$ 区间内的倍数存下来

然后套kruskal板子即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>

using namespace std;

#define ll long long

ll l,r;
ll par[1000005];

struct edge
{
	ll u,v,w;
};

vector<edge> e;

ll find(ll x)
{
	return par[x]==x?x:par[x]=find(par[x]);
}

bool cmp(edge a,edge b)
{
	return a.w<b.w;
}

ll n,m;
ll ans;

void kruskal()
{	
	for(ll i=0;i<e.size();i++)
	{
		ll u=find(e[i].u),v=find(e[i].v);
		
		if(u==v)
		{
			continue;
		}
		
		ans+=e[i].w;
		par[u]=v;
	}
	
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	cin>>l>>r;
	
    for(ll i=l;i<=r;i++)
	{
		par[i]=i;
	}
    for(ll i=1;i<=r;i++)  //存边
	{
        ll v=ceil(l*1.0/i)*i; //不小于L的第一个i的倍数
        for(ll j=v;j<=r;j+=i)
		{
            if(j!=v) //非自环
			{
				e.push_back({v,j,v*j/__gcd(v,j)});
			}
        }
    }
    
    sort(e.begin(),e.end(),cmp);
    
    kruskal(); //板子
    
    cout<<ans<<"\n";
    
	return 0;
}

Finished…

发表更新Problem Solutions3 分钟读完 (大约501个字)

题解：洛谷P8074 [COCI2009-2010#7] SVEMIR

虽然这是一道幽默的绿题，但是博主打AtCoder发现自己竟然不会写最小生成树，遂有此文

洛谷

前言

最小生成树

首先来看一下Kruskal最小生成树算法

【模板】最小生成树

将所有的边存下来，并按长度排序

用并查集存储两个点是否在同一棵树上，是则跳过；不是则合并，并将答案加上边长

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<bits/stdc++.h>

using namespace std;

#define ll long long

ll n,m;
ll cne; //生成树的边数 

struct edge
{
    ll u,v,w;
}e[2000005];

ll par[100005];
ll ans;
bool f; //是否能够生成 

ll find(ll x) //找根 
{
    return (par[x]==x)?x:par[x]=find(par[x]);	
}

bool cmp(edge a,edge b) //排序 
{
    return a.w<b.w;
}

void kruskal() //kruskal 
{
    
    for(ll i=1;i<=m;i++) //循环每一条边 
    {
        ll u=find(e[i].u),v=find(e[i].v);
        if(u==v) //同根则跳过 
        {
        	continue;
        }
		
        ans+=e[i].w;    
        par[u]=v; //合并 
        cne++;
        if(cne+1==n) //如果边数为点数-1，就结束 
		{
			f=1;
			break;
		}
    }
} 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
    cin>>n>>m;
    for(ll i=1;i<=n;i++) //init 
	{
		par[i]=i;
	}
    for(ll i=1;i<=m;i++)
    {
        cin>>e[i].u>>e[i].v>>e[i].w;
    }
    
    sort(e+1,e+m+1,cmp);
    
    kruskal();
    
	if(f==0)
	{
		cout<<"orz\n";
		return 0;
	}
	
    cout<<ans<<"\n";
    
    return 0;
}

思路

本题在上边的Kruskal模板上进行一个减边的优化即可

每个星球用三维坐标 $(x_i,y_i,z_i)$ 来表示，而在两个星球 $A,B$ 之间建造隧道的价格为 $\min{|x_A-x_B|,|y_A-y_B|,|z_A-z_B|}$。

所以考虑三个点 $a, b, c$ $(a_x<b_x<c_x) $ 此时连接 $ab$, $bc$ 更优，意思是说，我们会连的边一定是相邻的

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<bits/stdc++.h>

using namespace std;

#define ll long long

ll n,m;
ll cne;

struct edge
{
    ll u,v,w;
} e[2000005];

struct node
{
	ll x,y,z,id;
} a[2000005];

ll par[100005];
ll ans;

ll find(ll x)
{
    return (par[x]==x)?x:par[x]=find(par[x]);	
}

bool cmp1(node a,node b) //以三种坐标分别排序找相邻
{
    return a.x<b.x;
}
bool cmp2(node a,node b)
{
    return a.y<b.y;
}
bool cmp3(node a,node b)
{
    return a.z<b.z;
}

bool cmp(edge a,edge b)
{
    return a.w<b.w;
}

int dis(int x,int y)
{ 
	return min(abs(a[x].x-a[y].x),min(abs(a[x].y-a[y].y),abs(a[x].z-a[y].z)));
}

void kruskal()
{
    
    for(ll i=1;i<=m;i++)
    {
        ll u=find(e[i].u),v=find(e[i].v);
        if(u==v)
        {
        	continue;
		}
		
        ans+=e[i].w;    
        par[u]=v; 
        cne++;
        if(cne+1==n)
		{
			break;
		}
    }
} 

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
    cin>>n;
    for(ll i=1;i<=n;i++) //init 
	{
		par[i]=i;
	}
    for(ll i=1;i<=n;i++)
    {    	
        cin>>a[i].x>>a[i].y>>a[i].z;
		a[i].id=i;
    }
    
    sort(a+1,a+n+1,cmp1);
    for(ll i=1;i<n;i++)
    {
    	e[++m].u=a[i].id;
    	e[m].v=a[i+1].id;
    	e[m].w=dis(i,i+1);
	}
	
	sort(a+1,a+n+1,cmp2);
    for(ll i=1;i<n;i++)
    {
    	e[++m].u=a[i].id;
    	e[m].v=a[i+1].id;
    	e[m].w=dis(i,i+1);
	}
	
	sort(a+1,a+n+1,cmp3);
    for(ll i=1;i<n;i++)
    {
    	e[++m].u=a[i].id;
    	e[m].v=a[i+1].id;
    	e[m].w=dis(i,i+1);
	}
    
    sort(e+1,e+m+1,cmp);
    
    kruskal();
    
    cout<<ans<<"\n";
    
    return 0;
}
关注我

链接

分类

最新文章

归档

标签

Combinatorics1
Disjoint Set1
Dynamic Programming3
Euler's totient function1
Game Theory1
Graph Theory2
Monotonic queue1
Number theory1
Ordinary Generating Function1
Segment Tree4
Simulated Annealing1
Society1
Spanning Tree2
Teenagers1
Tree1

订阅更新

You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.

follow.it

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×