小黑

用户名：20190341315

访问量：8021

签　名：

菜！是真的菜，水题还做不全乎！菜。

等　　级
排　　名	126
经　　验	7718
参赛次数	8
文章发表	25
年　　龄	0
在职情况	学生
学　　校	郑州商学院
专　　业	计算机科学与技术

　　自我简介：

C/C++初学菜鸟

TA的其他文章

回文数(二)-题解（C语言代码）
浏览：81

数组排序 -题解（C++代码）STL+vector
浏览：329

1199: 哥德巴赫曾猜测素数打表
浏览：118

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

还是畅通工程-题解暴力AC+Kruskal算法

　　作者: 小黑　　　　发表时间：2020-12-29 12:01:13 浏览：404　|　评论：0　

原题链接：还是畅通工程

### 最小生成树模板题,但是这一题数据也太弱了;O(n^3)的都过了
### 第一个代码没用并查集就是纯暴力检查加边后是否有环路(这个写法不建议用,数据达到10^3以上妥妥的超时)
### 第二个代码用并查集检查加边后是否有环路，同时压缩路径(减少每一个元素到达祖先的查找次数)
## 暴力AC（O(n^3)）n：结点数
```javascript
#include<bits/stdc++.h>
using namespace std;
typedef struct st ak;
const int N=1e+3+10;
const int M=2e+5+10;
int e[N][N]={0};//邻接矩阵 
struct st{
	int v1,v2,w;
	st(){v1=v2=w=0;}
}s[M];
int n;
int m;//结点数 
int cmp(ak a,ak b)
{
	return a.w<b.w;
}
int find(int x,int y)
{//广搜从一个顶点出发
//从x出发能够到达y,说明x，y在一个连通分量中,return 0;
//否则 return 1; 
	int q[N]={0};
	int f=0,r=0;
	int book[N]={0};
	q[r++]=x;
	book[x]=1;
	while(f!=r)
	{
		int k=q[f++];
		for(int i=1;i<=m;i++)
		{
			if(!book[i]&&e[k][i]!=0)
			{
				book[i]=1;
				if(i==y)
				return 0;
				q[r++]=i;
			}
		}
	}
	return 1;
}
int main()
{
	int sum=0;
	int k=0;
	while(cin>>m&&m!=0)//m结点数,n边数 
	{
		memset(e,0,sizeof(e));
		sum=0;
		n=m*(m-1)/2;//边数
		for(int i=0;i<n;i++) 
		{
			int x,y,w;
			cin>>x>>y>>w;
			s[i].v1=x,s[i].v2=y,s[i].w=w;
		} 
		sort(s,s+n,cmp);//按权值从小到大排序 
		for(int i=0;i<n;i++)
		{
			int x,y,w;
			x=s[i].v1,y=s[i].v2,w=s[i].w;
			if(x==y)//自环 跳过 
			continue;
			if(find(x,y)==1)//判断x,y是否在一个联通分量中 
			{ 
				e[x][y]=w;
				e[y][x]=w;
				sum+=w;
			}
			else//在一个连通分量中,重边，选择权值最小的，作为边权 
			{//新权值小于原有权值 
			//更新x->y和y->x的权值 
				if(w<e[x][y])
				{
					sum-=e[x][y];
					e[x][y]=e[y][x]=w;
					sum+=w;
				}
			}
		}
	cout<<sum<<endl;
	}
	return 0;
}
```
## 最短路径+并查集+压缩路径（O(m*logm)）m：边数
```javascript
#include<bits/stdc++.h>
using namespace std;
const int N=5e+3+10; 
const int M=2e+5+10;
int pre[N]={0};
struct st{
	int v1,v2;//两个顶点 
	int w;//边权 
	st(){v1=v1=w=0;}//初始化(在这一题没什么用,但是定义时初始化是个好习惯噢！) 
}s[M];
int cmp(const st &a,const st &b)
{//sort的排序条件(比较权值决定传值的两个元素是否交换) 
	return a.w<b.w;
}
int find(int x)
{//找祖先 
	int t=x;
	while(pre[t]!=t)//只有祖先元素的值是自己(主函数里pre数组初始化每个数组元素都是自己的祖先) 
	{
		t=pre[t];//循环前往上一辈 
	}
	return t;//返回祖先 
}
int main()
{
	int n,m;//n:结点数 m:边数 
	int sum=0;//最小代价计数 
	int k=0;//最小生成树加入边数计数(n-1)
	//都一条边就有环路,少一条就不连通 
	int x,y,w;
	int t1,t2;
	while(cin>>n&&n!=0)
	{
		m=n*(n-1)/2;//边数
		sum=0;//多组数据输入，初始化一定不要忘了 
		k=0;
		for(int i=1;i<=n;i++)//初始化 
		{//每个元素都是自己的祖先 
			pre[i]=i;
		}
		for(int i=0;i<m;i++)
		{//记录每条边的两个顶点和权值 
			cin>>x>>y>>w;
			s[i].v1=x,s[i].v2=y;
			s[i].w=w;
		}
		sort(s,s+m,cmp);//按权值从小到大排序 
		/*
		从小到大排序后,循环时就可以优先选择边的权值小的边;
		然后循环中就不用考虑这个边是否是可加入最小的边;
		只需要判断加入这个边是否会形成环路; 
		*/ 
		for(int i=0;i<m;i++)
		{
			x=s[i].v1,y=s[i].v2;
			w=s[i].w;
			t1=find(x);//找祖先 
			t2=find(y);//找祖先 
			if(t1!=t2)//祖先不一样(生成树加入该边不会构成环路) 
			{
			
			k++;//生成树边数记录 
			sum+=w;//生成树权值累加 
			int f1,f2;
			pre[y]=t1;//让y认x的祖先为y的祖先 
			pre[t2]=t1;//让y的祖先也认x的祖先为自己的祖先 
			/*
			这就是压缩路径,使每个元素找到祖先(最上面的一级)的步骤减少;
			但是这样就找不到爸爸(离自己最近的上一级);因为所有元素都在尽可			能认祖先为爸爸,原来的爸爸就找不到了; 不过不影响这一的运作过				程; 
			*/
			}
			else//祖先一样,x，y属于一棵树(连通分支) 
			continue;
			if(k==n-1)//最小生成树形成,循环结束 
			break;
		}
		cout<<sum<<endl;
	}
	
	return 0;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

小黑

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C++代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

【计算两点间的距离】（C语言代码）

还是畅通工程-题解暴力AC+Kruskal算法

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言训练-舍罕王的失算（C语言代码）

C二级辅导-统计字符（C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言训练-素数问题（C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

1009题解

1050题解（结构体数组与结构体指针的使用）

小黑

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C++代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

【计算两点间的距离】 （C语言代码）

还是畅通工程-题解 暴力AC+Kruskal算法

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言训练-舍罕王的失算 （C语言代码）

C二级辅导-统计字符 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言训练-素数问题 （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

1009题解

1050题解（结构体数组与结构体指针的使用）

【计算两点间的距离】（C语言代码）

还是畅通工程-题解暴力AC+Kruskal算法

　　评论区

C语言训练-舍罕王的失算（C语言代码）

C二级辅导-统计字符（C语言代码）

C语言训练-素数问题（C语言代码）