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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
5 0 8
0 1 1
0 2 1
0 3 1
0 4 1
1 4 100
1 2 100
2 3 100
3 4 100
5 0 4
0 1 1
0 2 1
0 3 1
0 4 1

1
2
3
202
-1

1
2
3
4
5
6
7
8
9
struct stu {
	int v1;
	int v2;
	int cost;
	bool operator<(const stu &a)const {
		return cost<a.cost;
	}
} edge[51];

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
78
79
80
81
82
83
84
#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;
}

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
#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;
}