对于最小生成树，我第一次遇到该类例题，从周六到周一，中间断断续续3天时间，牺牲了不少脑细胞，今天终于靠我自己的力量AC了！哈哈，纪念一下~~~~

参考资料：http://wenku.baidu.com/view/71525d2ded630b1c59eeb5bf.html（也是我感觉要比书上更直白、更详细的资料）

例题来源：南阳理工ACM-OJ：http://acm.nyist.net/JudgeOnline/problem.php?pid=38

//普里姆算法
#include//memset()
#include
#include
using namespace std;

#define MAX 501
#define X 0
#define Y 1
#define VALUE 2

int map[MAX][MAX];
int prevex[MAX];//记录与建立最小生成树可连接的顶点，属于Tree的标记-1
int lowcost[MAX];//记录nearvex[i]的权值

void swap(int &a,int &b)
{
    a=a+b;
    b=a-b;
    a=a-b;
}

int Prim(int v,int e)//顶点数，边数
{
    int i, j, sum = 0;
    int min = 100;
    int a,b;
    for( i=1; i<=e; i++)
    {
        cin >>a >>b;
        //if(b < a)swap(a,b);
        cin >>map[a][b];
        map[b][a] = map[a][b];
    }

    prevex[0] = 1;    //初始顶点为1
    prevex[1] = -1;
    for( i=1; i
    {
        //k = search();
        for( j=1; j<=v; j++)
        {
            if(prevex[0] == j)continue;
            if(!map[prevex[0]][j])continue;
            if(lowcost[j] > 0 && map[prevex[0]][j] > lowcost[j])continue;
            if(prevex[j] != -1)    //如果顶点j不在MST里
            {
                if(lowcost[j])
                if(lowcost[j] < map[prevex[0]][j])continue;
                lowcost[j] = map[prevex[0]][j];
                prevex[j] = prevex[0];
            }
        }
        //
        min = 100;
        int jj = 0;
        for( j=1; j<=v; j++)
        {
            if(!lowcost[j] || prevex[j] == -1)continue;
            if(lowcost[j] < min)
            {
                jj = j;
                min = lowcost[j];
            }
        }
        sum += min;
        prevex[jj] = -1;
        //下一个搜索点
        prevex[0] = jj;
    }
    return sum;
}

int main()
{
    int n,v,e;
    int i,s=100,sum;
    cin>>n;
    while(n--)
    {
        cin >>v >>e;
        //memset(memset,0,sizeof(memset));
        memset(lowcost,0,sizeof(lowcost));
        memset(prevex,0,sizeof(prevex));

        sum = Prim(v,e);//构造MST
        
        for(i=1; i<=v; i++)
        {
            cin>>e;
            if(e < s)swap(e,s);
        }
        cout<< s+sum <<endl;
    }
    return 0;
}