__周赛（最小生成树（Prime））

将已经链接的边的权值设为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 }