按E搞比利

用户名：1096581839

访问量：8653

签　名：

重度抑郁,休学在家,无聊学编程

等　　级
排　　名	1997
经　　验	2513
参赛次数	0
文章发表	22
年　　龄	20
在职情况	学生
学　　校	中国计量大学
专　　业	数学

　　自我简介：

一个重度抑郁症患者,已经吃药两年.......

TA的其他文章

[搞比利]2048题-46.多重背包-题解(C++代码)
浏览：319

[搞比利]2049题-53.最短路练习-题解弗洛里达算法(C++代码)
浏览：388

[搞比利]克鲁斯卡尔算法2050题-55.战争通讯-题解(C++代码)
浏览：493

你可能喜欢

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

gets函数前有scanf读取时候，会读取缓存回车导致出错！！！

[搞比利]克鲁斯卡尔算法2050题-55.战争通讯-题解(C++代码)

　　作者: 按E搞比利　　　　发表时间：2019-12-05 01:27:09 浏览：493　|　评论：0　

原题链接：战争通讯

//这题是真的丧病
	//卡了我好长时间
	#include<bits/stdc++.h>
	using namespace std;
	int cost[10086];//记录花费
	bool CNM[10086];//纪录是否有电台
	int father[10086];//记录他爸
	struct fuck{
	int s;
	int e;
	int cost;};//这是边
	fuck edge[10086];
	bool cao(fuck a,fuck b){//重新定义排序
		return a.cost<b.cost;}
	int getfather(int a){//找根祖
	int x=a;
	if(father[x]==x)
		return x;
	else
		getfather(father[x]);
	}
	int main(){
	int n,i,j,pos=0;
	int 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,edge+pos+1,cao);//排序
	for(i=1;i<=pos;i++){//剩下的就是繁杂冗长的分类讨论了,真J8坑
		if(getfather(edge[i].s)!=getfather(edge[i].e)){//&&edge[i].s!=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)]){//cost szui da
				
				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].e)]&&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)]){//cost szui da
				
	
				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)]){//cost szui da
				CNM[getfather(edge[i].e)]=1;
				CNM[getfather(edge[i].s)]=0;
				
				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)]){//cost szui da
				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;	}

0.0分

1 人评分

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

按E搞比利

TA的其他文章

你可能喜欢

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

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

不容易系列（C语言代码）

gets函数前有scanf读取时候，会读取缓存回车导致出错！！！

[搞比利]克鲁斯卡尔算法2050题-55.战争通讯-题解(C++代码)

评论区

精彩推荐

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

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

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

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

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

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

Tom数（C语言代码）

计算质因子（C语言代码）

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

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

按E搞比利

TA的其他文章

你可能喜欢

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

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

不容易系列 （C语言代码）

gets函数前有scanf读取时候，会读取缓存回车导致出错！！！

[搞比利]克鲁斯卡尔算法2050题-55.战争通讯-题解(C++代码)

评论区

精彩推荐

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

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

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

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

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

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

Tom数 （C语言代码）

计算质因子 （C语言代码）

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

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

不容易系列（C语言代码）

　　评论区

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

Tom数（C语言代码）

计算质因子（C语言代码）