将已经链接的边的权值设为0即可。
但是可能会超时，提交的时候，有一次显示超时，所以这个解法是有问题的，看到有171ms的，实力差的太大了，还是得使劲刷题。
/*2015-5-18 951ms*/
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define INF 0x3f3f3f3f int map[510][510],p[510],n; int prime(){ int visit[510]; int less[510]; int nodes,sum; sum = 0;nodes = 1; memset(visit,0,sizeof(visit)); visit [1] = 1; for(int i = 1;i<=n;i++){ less[i] = map[1][i]; } int temp,k; for(int i = 1;i<=n;i++){ temp = INF; for(int j = 1;j<=n;j++){ if(!visit[j] && temp > less[j]) temp = less[k=j]; } if(temp == INF)break; nodes++; sum += less[k]; visit[k] = 1; for(int j = 1;j<=n;j++){ if(!visit[j] && less[j] > map[k][j]) less[j] = map[k][j]; } } // printf("%d\n",nodes); if(nodes == n)return sum; else return -1; } int main() { int t ; scanf("%d",&t); while(t--){ int m,k; memset(map,INF,sizeof(map)); scanf("%d%d%d",&n,&m,&k); for(int i = 0;i<m;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); map[a][b] = map[b][a] = min(map[a][b],c); } for(int i = 0;i<k;i++){ int d; scanf("%d",&d); int x[510]; for(int j =0;j<d;j++){ scanf("%d",&x[j]); } for(int j = 0;j<d-1;j++) for(int jj = j+1;jj<d;jj++) map[x[j]][x[jj]] = map[x[jj]][x[j]] = 0; } printf("%d\n",prime()); } }
1 /*这个代码还是比较给力的，这个是利用了Prime算法的特点，将连起来的点构成链，2015-5-18 717ms*/
2 #include<stdio.h>
3 #include<string.h>
4 #include<algorithm>
5 using namespace std;
6
7 #define INF 0x3f3f3f3f
8
9 int map[510][510],p[510],n;
10
11
12 int prime(){
13
14 int visit[510];
15 int less[510];
16
17 int nodes,sum;
18
19 sum = 0;nodes = 1;
20
21 memset(visit,0,sizeof(visit));
22
23 visit [1] = 1;
24
25 for(int i = 1;i<=n;i++){
26
27 less[i] = map[1][i];
28 }
29 int temp,k;
30 for(int i = 1;i<=n;i++){
31
32 temp = INF;
33 for(int j = 1;j<=n;j++){
34 if(!visit[j] && temp > less[j])
35 temp = less[k=j];
36 }
37 if(temp == INF)break;
38 nodes++;
39 sum += less[k];
40
41 visit[k] = 1;
42
43 for(int j = 1;j<=n;j++){
44 if(!visit[j] && less[j] > map[k][j])
45 less[j] = map[k][j];
46 }
47
48 }
49 // printf("%d\n",nodes);
50 if(nodes == n)return sum;
51 else return -1;
52
53 }
54
55
56 int main() {
57
58 int t ;
59
60 scanf("%d",&t);
61
62 while(t--){
63
64 int m,k;
65
66 memset(map,INF,sizeof(map));
67
68 scanf("%d%d%d",&n,&m,&k);
69
70 for(int i = 0;i<m;i++){
71
72 int a,b,c;
73
74 scanf("%d%d%d",&a,&b,&c);
75
76 map[a][b] = map[b][a] = min(map[a][b],c);
77
78 }
79 for(int i = 0;i<k;i++){
80 int d;
81
82 scanf("%d",&d);
83
84 int x,last;
85
86 scanf("%d",&last);
87 for(int j =2;j<=d;j++){
88
89 scanf("%d",&x);
90 map[x][last] = map[last][x] = 0;
91 last = x;
92 }
93
94 }
95 printf("%d\n",prime());
96
97 }
98
99
100
101 }
