2021天梯赛训练-8——7-11 特殊最小成本修路 (10分)请大佬指正

63 阅读 0 评论 42 点赞

我是靠谱客的博主痴情白昼，最近开发中收集的这篇文章主要介绍2021天梯赛训练-8——7-11 特殊最小成本修路 (10分)请大佬指正，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

n个城镇之间目前有一些道路连接，但道路都是年久失修的土道。现在政府准备将其中一些土道改造为标准公路，希望标准公路能够将所有城镇连通且总成本最小，但其中有一个城镇比较特殊，受地形等限制，最多只能有两条标准公路通过该镇。请编写程序，找出一种满足上述条件的、总成本最小的改造方案，若不存在改造方案，则亦能识别。假定道路是双向的。

输入格式:
输入包含多组数据。每组数据第一行是3个整数n、v和e，均不超过50，n为城镇数目，城镇编号0至n-1。v为最能有两条标准公路的城镇编号，e为现有的土路条数，接下来是e行表示每条道路信息，每行为3个非负整数a、b、c，表示城镇a和城镇b间现有一条道路，若将其改造为标准公路，成本为c。

输出格式:
对每组数据输出一行，为一个整数，表示满足要求的最小成本，若不存在改造方案，则输出-1。

输入样例:

输出样例:

202
-1

思路
疑惑点1：
关于结构体按修路的花费排序，如果写成

struct stu {
	int v1;
	int v2;
	int cost;
	bool operator<(const stu &a)const {
		return cost<a.cost;
	}
} edge[51];

用重载 < 运算符，而不用sort排序，0分，为什么，不明白，望大佬讲解。。。
疑惑点2：（训练营里有人提出的测试点）
4 0 4
0 1 1
0 2 1
0 3 1
1 2 2
然而我下面的代码（分特殊城镇修1条和修路2条讨论）
得出来是4 但是提交了答案错误，一个测试点也过不去。。。。。。

我很想知道这题的后台测试点。。。。谜一样。。。。。。
代码

#include <bits/stdc++.h>
using namespace std;
struct stu {
	int v1;
	int v2;
	int cost;
};
vector<stu> edge,edge1;
int xx[51],sum=0,visit[51];
int cmp(stu a,stu b){
	return a.cost<b.cost;
}
int find(int x) {
	if(xx[x]==x) return x;
    xx[x]=find(xx[x]);
	return xx[x];
}
int fun(int m,int n){
	int i,j,sum1=0;
	for(i=0,j=0;i<edge.size()&&j<n-m;i++){
		int v1=find(edge[i].v1);
		int v2=find(edge[i].v2);
		if(v1!=v2){
			xx[v2]=v1;
			j++;
			visit[edge[i].v1]=1;
			visit[edge[i].v2]=1;
			sum1+=edge[i].cost;
		}		
	}
	set<int> num;
	for(int i=0;i<n;i++){
		num.insert(xx[i]);
	}
	if(num.size()==1) return sum1;
	else return -1;
}
int main() {
	int n,v,e;
	while(cin>>n>>v>>e) { 
		stu x;
		edge.resize(0);
		edge1.resize(0);
		int flag1=-1,flag2=-1,sum1,sum2;
		for(int i=0;i<e;i++){
			cin>>x.v1>>x.v2>>x.cost;
			sum+=x.cost;
			if(x.v1!=v&&x.v2!=v) edge.push_back(x);
			else edge1.push_back(x);
		}
        sort(edge1.begin(),edge1.end(),cmp);
        sort(edge.begin(),edge.end(),cmp);
		for(int i=0;i<51;i++) xx[i]=i;
		//特殊城镇只修一条路
		xx[edge1[0].v1]=v;
		xx[edge1[0].v2]=v; 
		sum1=edge1[0].cost;
		flag1=fun(2,n);
		if(flag1!=-1){
			sum1+=flag1;
			if(sum1<sum) sum=sum1;
		}
		//特殊城镇修两条路
		for(int i=0;i<edge1.size()-1;i++){
			for(int j=i+1;j<edge1.size();j++){
				sum2=0;
				for(int i=0;i<51;i++) xx[i]=i;
				sum2+=edge1[i].cost+edge1[j].cost;	
				xx[edge1[i].v1]=xx[edge1[i].v2]=xx[edge1[j].v1]=xx[edge1[j].v2]=v;
				int mm=fun(3,n);
				if(mm!=-1){
					flag2=1;
					sum2+=mm;
					if(sum2<sum) sum=sum2;
					
				}
			}
		} 
		if(flag1!=-1||flag2!=-1) cout<<sum<<endl;
		else cout<<-1<<endl;
	}
	return 0;
}

AC代码

#include <bits/stdc++.h>
using namespace std;
struct stu {
	int v1;
	int v2;
	int cost;
} edge[51];
int xx[51];
int find(int x) {
	if(xx[x]==-1) return x;
    xx[x]=find(xx[x]);
	return xx[x];
}
int cmp(stu a,stu b){
	return a.cost<b.cost;
}
int main() {
	int n,v,e,a,b,c;
	while(cin>>n>>v>>e) {
		for(int i=0; i<e; i++){
			cin>>a>>b>>c;
			edge[i].v1=a;
			edge[i].v2=b;
			edge[i].cost=c;
		}
        sort(edge,edge+e,cmp);
		int visit[n];
		memset(visit,0,sizeof(visit));
		memset(xx,-1,sizeof(xx));
		int sum=0,i,j;
		for(i=0,j=0; i<e&&j<n-1; i++){
			int v1=find(edge[i].v1);
			int v2=find(edge[i].v2);
			if(v1!=v2) {
                if((edge[i].v1==v||edge[i].v2==v)&&visit[v]>=2) continue;
                visit[edge[i].v1]++;
			    visit[edge[i].v2]++;
				xx[v2]=v1;
				j++;
				sum+=edge[i].cost;
			}
		}
		if(j==n-1) cout<<sum<<endl;
		else cout<<-1<<endl;
	}
	return 0;
}