devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

程序设计思维与实践 week6 氪金带东、戴好口罩！、掌握魔法の东东 I、数据中心、最小生成树最大边最小证明_最小生成树 最大边权最小 证明

作者：我家小花儿 | 2024-03-05 18:16:38

赞

踩

最小生成树 最大边权最小 证明

文章目录

一，氪金带东

描述

实验室里原先有一台电脑(编号为1)，最近氪金带师咕咕东又为实验室购置了N-1台电脑，编号为2到N。每台电脑都用网线连接到一台先前安装的电脑上。但是咕咕东担心网速太慢，他希望知道第i台电脑到其他电脑的最大网线长度，但是可怜的咕咕东在不久前刚刚遭受了宇宙射线的降智打击，请你帮帮他。
在这里插入图片描述提示: 样例输入对应这个图，从这个图中你可以看出，距离1号电脑最远的电脑是4号电脑，他们之间的距离是3。 4号电脑与5号电脑都是距离2号电脑最远的点，故其答案是2。5号电脑距离3号电脑最远，故对于3号电脑来说它的答案是3。同样的我们可以计算出4号电脑和5号电脑的答案是4.

输入

输入文件包含多组测试数据。对于每组测试数据，第一行一个整数N (N<=10000)，接下来有N-1行，每一行两个数，对于第i行的两个数，它们表示与i号电脑连接的电脑编号以及它们之间网线的长度。网线的总长度不会超过10^9，每个数之间用一个空格隔开。

输出

对于每组测试数据输出N行，第i行表示i号电脑的答案 (1<=i<=N).

example

输入

5
1 1
2 1
3 1
1 1

  • 1
  • 2
  • 3
  • 4
  • 5

输出

3
2
3
4
4

  • 1
  • 2
  • 3
  • 4
  • 5

思路

简要概括题意，我们需要找到在电脑组成的无向图中每个顶点到边缘的最长距离。我们使用三次dfs搜索。第一遍dfs以电脑1为源点，遍历过程中记录路径最长的端点编号。第一遍dfs后我们找到图直径的一个端点d。

第二遍dfs我们以d为源点，再次寻找最远点（图直径的另一个端点），在此过程中我们在**数组b[i]**中记录d到每一个点的距离 （第二遍dfs结束后d被更新为图直径的另一个端点）。

第三遍dfs，我们以图直径的另一个端点为源点，在**数组e[i]**中记录端点到每一个点的距离。**max(b[i],e[i])**便是顶点i到图边缘的最长距离。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=1e6+5;
struct edge{//链式前向星； 
	int u,v,w,next;
	edge(){};
}E[maxn];
int vis[maxn];
int head[maxn];
int b[maxn],e[maxn];
int tot,d;//总线段长度以及端点号 

void init(int n)
{//图初始化,无边； 
	tot=0;
    for(int i=0; i<n; i++)
	    head[i]=-1; 
}

void add(int u,int v,int w)
{//建图； 
    E[tot].u=u;
	E[tot].v=v;
	E[tot].w=w;
	E[tot].next=head[u];//指向上一个边id；	
	head[u]=tot;
	tot++;
}

void find(int u,int length, int *len)
{//dfs记录到u点的长度，结果存储在d中 
    len[u]=length;
    if(len[d]<len[u])d=u;//最长的路径对应端点； 
	for(int i=head[u]; i!=-1; i=E[i].next){
		if(vis[E[i].v] != 1){
			vis[E[i].v] =1;
			find(E[i].v,length+E[i].w,len);
		}
	}
} 

int main()
{
	int n,u,v,w;
	while(scanf("%d",&n)!=EOF)
	{
	    init(n+1);
		for(int i=2;i<=n;i++){
			scanf("%d%d",&v,&w);
			add(i,v,w);
			add(v,i,w);
		}	
		//从1出发寻找端点1
		memset(vis,0,sizeof(vis)); 
		b[d]=0;
		vis[1]=1;
		find(1,0,b);
		//d已变为端点1，寻找端点2，同时记录端点1到各点长度 
		memset(vis,0,sizeof(vis)); 
		b[d]=0;
		vis[d]=1;
		find(d,0,b);
		//记录端点2到各点长度
		memset(vis,0,sizeof(vis));
		e[d]=0;
		vis[d]=1;
		find(d,0,e);
		
		for(int i=1;i<=n;i++)
		    cout<<max(b[i],e[i])<<endl; 
	}
	return 0;
}

  • 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

二，戴好口罩！

描述

新型冠状病毒肺炎（Corona Virus Disease 2019，COVID-19），简称“新冠肺炎”，是指2019新型冠状病毒感染导致的肺炎。
如果一个感染者走入一个群体，那么这个群体需要被隔离！

小A同学被确诊为新冠感染，并且没有戴口罩！！！！！！
危！！！时间紧迫！！！！需要尽快找到所有和小A同学直接或者间接接触过的同学，将他们隔离，防止更大范围的扩散。

众所周知，学生的交际可能是分小团体的，一位学生可能同时参与多个小团体内。请你编写程序解决！戴口罩！！

输入

多组数据，对于每组测试数据：
第一行为两个整数n和m（n = m = 0表示输入结束，不需要处理），n是学生的数量，m是学生群体的数量。0 < n <= 3e4 ， 0 <= m <= 5e2；
学生编号为0~n-1，小A编号为0。随后，m行，每行有一个整数num即小团体人员数量。随后有num个整数代表这个小团体的学生。

输出

输出要隔离的人数，每组数据的答案输出占一行

example

输入

100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

输出

4
1
1

  • 1
  • 2
  • 3

思路

题中的小群体可以用并查集的思想描述。我们用数组**par[maxn]来记录每个学生所在群体的代表元，用数组num[maxn]**来记录每一个学生代表所在群体的人的数量。

初始化并查集，每个学生是自身的代表元，每个学生团体的人数为1。

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

每个小团体内学生进行并查集合并，unite(int x,int y) 函数将学生x，y所在的团体合并（因为x，y现在属于同一个团体）。合并过程中我们将数量小的集合合并到数量大的集合上，让集合尽量平衡（有点平衡搜索树合并的感觉）。 find(int x) 函数返回学生x所在团体的代表元，搜索过程中使用路径压缩降低后续搜索时间。最后返回 **num[find(0)]**即感染者所在团体的人数。

int find(int x)
{//路径压缩以减少后续搜索时间
	return par[x]==x? x:par[x]=find(par[x]);
}
void unite(int x,int y){//并查集合并；
	x=find(x);
	y=find(y);
	if(x==y)return;
	if(num[x]>num[y])swap(x,y);//小树向大树合并； 
	par[x]=y;
	num[y] += num[x]; 
	num[x]=num[y];
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=3e4+10;
int par[maxn];//并查集代表元
int num[maxn];//集合大小 

void init(int n){
	for(int i=0; i<n; i++){
	    par[i]=i;
	    num[i]=1;
	 } 
} 
/*
int find(int x){
    while(par[x]!=x){
    	par[x]=par[par[x]];
    	x=par[x];
	}
    return x;
}
*/
int find(int x)
{//路径压缩以减少后续搜索时间
	return par[x]==x? x:par[x]=find(par[x]);
}

void unite(int x,int y){//并查集合并；
	x=find(x);
	y=find(y);
	if(x==y)return;
	if(num[x]>num[y])swap(x,y);//小树向大树合并； 
	par[x]=y;
	num[y] += num[x]; 
	num[x]=num[y];
}

int main()
{
	int n,m;
	while(1)
	{
		scanf("%d%d",&n,&m);
		if(n==0&&m==0)break;
	    init(n);
		while(m--)
		{
			int N,last=-1;//p个人 
			scanf("%d",&N);
			for(int i=0;i<N;i++)
			{
				int p;
				scanf("%d",&p);
				if(last!=-1)unite(p,last);
				last=p;
			}
		}	
		cout<<num[find(0)]<<endl;
	}
	return 0;
}


  • 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

三，掌握魔法の东东 I

描述

东东在老家农村无聊，想种田。农田有 n 块，编号从 1~n。种田要灌氵
众所周知东东是一个魔法师，他可以消耗一定的 MP 在一块田上施展魔法，使得黄河之水天上来。他也可以消耗一定的 MP 在两块田的渠上建立传送门，使得这块田引用那块有水的田的水。 (1<=n<=3e2)
黄河之水天上来的消耗是 Wi，i 是农田编号 (1<=Wi<=1e5)
建立传送门的消耗是 Pij，i、j 是农田编号 (1<= Pij <=1e5, Pij = Pji, Pii =0)
东东为所有的田灌氵的最小消耗

输入

第1行：一个数n
第2行到第n+1行：数wi
第n+2行到第2n+1行：矩阵即pij矩阵

输出

东东最小消耗的MP值

example

输入

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

输出

9

  • 1

思路

有顶点，有边权，无向图，求最小 - - - - - - ->kruscal。 无论如何都要有水源，则可将黄河之水作为新的顶点加入图中，其到每个顶点（每块农田）都有一条边，边权为对应的黄河之水的消耗量，之后得到新图。边我们用前向星表达，并按照边权大小重载运算符以实现对边按边权大小升序排序。

接下来是利用kruscal求最小生成树，其中还是利用并查集的思想避免出现环，对已经加入生成树的元素我们将其看做一个集合团体，后续加入的边不能构成环，即我们要从未加入的边中选择一个加入后不构成环的边权最小的边。

建树过程中ans累加每一条加入边的边权，最后输出答案。

for(int i=0;i<cnt;i++)
	{//kruscal 
		if(count==n)break;
		if(father(a[i].from)!=father(a[i].to))
		{//不在一个并查集中，不构成环； 
			unite(a[i].from,a[i].to);//合并 
			ans+=a[i].dis;
			count++;
		}
	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
using namespace std;
/*
农田灌溉问题，添加源点，将水源作为点加入农田 
最小生成树；
*/
const int maxn=1e6;
int f[maxn];//并查集；
int n,w,p; 
struct edge
{//存每条边的源点和终点以及权重，并按照边权升序； 
	int from,to,dis;
	edge(){};//构造函数； 
	edge(int a,int b,int c){
	   from =a;
	   to=b;
	   dis=c;
	}  
	bool operator<(const edge &a){
		return dis<a.dis;
	}
}a[maxn]; 

int father(int x)
{//代表元； 
	while(f[x]!=x){
		f[x]=f[f[x]];
		x=f[x];
	}
	return x;
}
void unite(int x,int y)
{//合并； 
	f[father(y)]=father(x);
}

int main()
{
	scanf("%d",&n);
	int cnt=0;
	//黄河之水边权； 
	for(int i=0;i<n;i++){
		scanf("%d",&w);
		a[cnt++]=edge(n,i,w);
		a[cnt++]=edge(i,n,w);
	}
	//通道边权； 
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			scanf("%d",&p);
			a[cnt++]=edge(i,j,p);
		}
	} 
	sort(a,a+cnt);//按照边权升序； 
	int ans=0,count=0;
	for(int i=0;i<=n;i++){//初始化并查集； 
		f[i]=i;
	}
	for(int i=0;i<cnt;i++)
	{//kruscal 
		if(count==n)
			break;
		if(father(a[i].from)!=father(a[i].to))
		{//不在一个并查集中，不构成环； 
			unite(a[i].from,a[i].to);//合并 
			ans+=a[i].dis;
			count++;
		}
	}
	printf("%d\n",ans);
	return 0;
}

  • 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

四，数据中心

描述

在这里插入图片描述

输入

在这里插入图片描述

输出

在这里插入图片描述

example

输入

4
5
1
1 2 3
1 3 4
1 4 5
2 3 8
3 4 2

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

输出

4

  • 1

在这里插入图片描述

思路

总结题意，我们要寻找一个生成树，其中该树的最大边权最小。
直接用kruscal构造一下，输出最大边权即可。

代码

#include<iostream>
#include<cstdio>
#include<stdio.h> 
#include<algorithm>
#include<cstring>
using namespace std;
/*
所有点都相连，即生成树；
根据定义求生成树中的最小的最大边权 
*/ 
const int maxn=1e6;
int f[maxn];//并查集；
int n,m,root; 
struct edge
{//存每条边的源点和终点以及权重，并按照边权升序； 
	int from,to,dis;
	edge(){};//构造函数； 
	edge(int a,int b,int c){
	   from =a;
	   to=b;
	   dis=c;
	}  
	bool operator<(const edge &a){
		return dis<a.dis;
	}
}a[maxn]; 

int father(int x){
	while(f[x]!=x){
		f[x]=f[f[x]];
		x=f[x];
	}
	return x;
}

void unite(int x,int y)
{//合并； 
	f[father(y)]=father(x);
}

int main()
{
	cin>>n>>m>>root; 
	for(int i=0;i<m;i++){
		scanf("%d%d%d",&a[i].from,&a[i].to,&a[i].dis);
	}
	sort(a,a+m);//边权升序； 
	for(int i=1;i<=n;i++)
		f[i]=i;
	int maxt=0,cnt=0;
	for(int i=0;i<m;i++)
	{//kruscal; 
		if(cnt==n-1)
			break;
		if(father(a[i].from)!=father(a[i].to))
		{//不构成环； 
			maxt=max(maxt,a[i].dis);//最大边权； 
			unite(a[i].from,a[i].to);
			cnt++;
		}
	}
	cout<<maxt;
	return 0;
}

  • 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

五，总结

1,图论中一般结论需要记住，比如第一题用到的任一点向图边缘遍历，最远到达的点为图直径的端点。最后一题中的带权无向图中最大边权最小的生成树是最小生成树（详细证明后续给出）。
2，写并查集时可以进行路径压缩，以减少后续搜索的时间。

六，涉及证明

在这里插入图片描述在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/192921
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号

        
cppcmd=keepalive&