少年Q

用户名：yin19990129

访问量：25359

签　名：

这次一定不水了！

等　　级
排　　名	181
经　　验	6821
参赛次数	2
文章发表	71
年　　龄	21
在职情况	学生
学　　校	宿迁学院
专　　业	软件工程

　　自我简介：

TA的其他文章

15.合并区间-题解(C++代码)只做最好的思路！
浏览：821

16.求逆序对个数-题解(C++代码)只做最好的思路！
浏览：1845

[STL训练]sort练习-题解(C++代码)只做最好的思路！
浏览：623

你可能喜欢

55.战争通讯-题解（C++代码）只做最好的思路！

　　作者: 少年Q　　　　发表时间：2020-05-04 22:28:30 浏览：243　|　评论：0　

原题链接：战争通讯

这题真的是一言难尽--很难搞。。。对最小生成树还不是太掌握的我，碰到这题自然就卡住了。。根据这个题给出的邻接矩阵画出了带权值图，并且进一步画出了最小生成树，是一个具有线性结构的树，，有点像链表，至于思考部分我就想到这里，关于如何实现这个题，我暂时没有想出好的思路来码这题，我参考了大神网友的代码后，由衷的佩服，经过对大神网友的代码分析和学习后，自己尝试码了一遍，代码如下：
```cpp
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
using namespace std;
int cost[10005];//记录花费 
int father[10005]; //记录父节点 
bool cnm[10005];//记录电台 
struct eg{
	int s;
	int e;
	int cost;
}edge[10005];//边 
bool cmp(eg x,eg y){
	return x.cost<y.cost;
}
int getfather(int a){//找根祖 
	int x=a;
	if(father[x]==x){
		return x;
	}else{
		return getfather(father[x]);
	}
}
int main(){
	int i,j,n,pos=0,ans=0;
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>cost[i];
		father[i]=i;
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			pos++;
			edge[pos].s=i;
			edge[pos].e=j;
			cin>>edge[pos].cost;
		}
	}
	sort(edge+1,edge+pos+1,cmp);
	for(i=1;i<=pos;i++){
		if(getfather(edge[i].s)!=getfather(edge[i].e)){
		//分类枚举，有点小恶心。。 
			if(cnm[getfather(edge[i].s)]==1&&cnm[getfather(edge[i].e)]==1){
				if(edge[i].cost<=cost[getfather(edge[i].s)]&&cost[getfather(edge[i].e)]<=cost[getfather(edge[i].s)]){
    				cnm[getfather(edge[i].s)]=0;
    				ans+=edge[i].cost;
    				ans-=cost[getfather(edge[i].s)];
    				father[getfather(edge[i].s)]=getfather(edge[i].e);
    			}else if(edge[i].cost<=cost[getfather(edge[i].s)]&&cost[getfather(edge[i].e)]>=cost[getfather(edge[i].s)]){
    				cnm[getfather(edge[i].e)]=0;
    				ans+=edge[i].cost;
    				ans-=cost[getfather(edge[i].e)];
    				father[getfather(edge[i].e)]=getfather(edge[i].s);
    			}else{
    				continue;
    			}
			}else if(cnm[getfather(edge[i].s)]==0&&cnm[getfather(edge[i].e)]==1){
				if(edge[i].cost<=cost[getfather(edge[i].e)]&&cost[getfather(edge[i].e)]>=cost[getfather(edge[i].s)]){
					cnm[getfather(edge[i].e)]=0;
					cnm[getfather(edge[i].s)]=1;
					ans+=edge[i].cost;
					ans-=cost[getfather(edge[i].e)];
					ans+=cost[getfather(edge[i].s)];
					father[getfather(edge[i].e)]=getfather(edge[i].s);
				}else if(edge[i].cost<=cost[getfather(edge[i].s)]&&cost[getfather(edge[i].e)]<=cost[getfather(edge[i].s)]){
					ans+=edge[i].cost;
					father[getfather(edge[i].s)]=getfather(edge[i].e);
				}else{
					cnm[getfather(edge[i].s)]=1;
					ans+=cost[getfather(edge[i].s)];
				}
			}else if(cnm[getfather(edge[i].s)]==1&&cnm[getfather(edge[i].e)]==0){
				if(edge[i].cost<=cost[getfather(edge[i].e)]&&cost[getfather(edge[i].e)]>=cost[getfather(edge[i].s)]){
					ans+=edge[i].cost;
					father[getfather(edge[i].e)]=getfather(edge[i].s);
				}else if(edge[i].cost<=cost[getfather(edge[i].s)]&&cost[getfather(edge[i].e)]<=cost[getfather(edge[i].s)]){
					cnm[getfather(edge[i].s)]=0;
					cnm[getfather(edge[i].e)]=1;
					ans+=edge[i].cost;
					ans-=cost[getfather(edge[i].s)];
					ans+=cost[getfather(edge[i].e)];
					father[getfather(edge[i].s)]=getfather(edge[i].e);
				}else{
					cnm[getfather(edge[i].e)]=1;
					ans+=cost[getfather(edge[i].e)];
				}
			}else{
			      if(edge[i].cost<=cost[getfather(edge[i].s)]&&cost[getfather(edge[i].e)]<=cost[getfather(edge[i].s)]){
                     cnm[getfather(edge[i].e)]=1;
                     ans+=edge[i].cost;
                     ans+=cost[getfather(edge[i].e)];
                     father[getfather(edge[i].s)]=getfather(edge[i].e);
				   }
                   else if(edge[i].cost<=cost[getfather(edge[i].e)]&&cost[getfather(edge[i].e)]>=cost[getfather(edge[i].s)]){    
                     cnm[getfather(edge[i].s)]=1;
                     ans+=edge[i].cost;
                     ans+=cost[getfather(edge[i].s)];
                     father[getfather(edge[i].e)]=getfather(edge[i].s);
				   }else {
                      cnm[getfather(edge[i].s)]=1;
                      cnm[getfather(edge[i].e)]=1;
                      ans+=cost[getfather(edge[i].s)];
                      ans+=cost[getfather(edge[i].e)];
				   }
			}
		}
	} 
	cout<<ans;
	return 0;
}
```

0.0分

2 人评分

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

少年Q

TA的其他文章

你可能喜欢

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

点我有惊喜！你懂得！

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

简单的a+b （C语言代码）

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

55.战争通讯-题解（C++代码）只做最好的思路！

评论区

精彩推荐

简单的a+b （C语言代码）

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

图形输出（C语言代码）

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

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

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

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

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

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

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

少年Q

TA的其他文章

你可能喜欢

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

点我有惊喜！你懂得！

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

简单的a+b （C语言代码）

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

55.战争通讯-题解（C++代码）只做最好的思路！

评论区

精彩推荐

简单的a+b （C语言代码）

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

图形输出 （C语言代码）

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

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

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

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

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

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

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

　　评论区

图形输出（C语言代码）