__周赛（最小生成树（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
",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
",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
",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
",prime());
 96         
 97     }
 98     
 99     
100     
101 }