最小生成树（求村落之间最小修哪几条路能使耗资最小）

大佬的博客

http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<algorithm>
#include<map>
#define maxn 200005
#define inf 1e8
using namespace std;
//普里姆算法    o（n*n）    也可以用优先队列存储   o（n*logn）
int cost[1000][1000];//记录两点间的权值
int mincost[10000];//从集合x出发到每个顶点的最小权值
bool used[100000];//顶点是否在集合中
int v;//顶点数
int prim()
{
    for(int i=0;i<v;i++)//初始化mincost和used
    {
        mincost[i]=inf;
        used[i]=false;
    }
    mincost[0]=0;
    int res=0;//求和
    while(true||1)
    {
        int s=-1;
        for(int u=0;u<v;u++)
        {
            if(!used[u]&&(s==-1||mincost[u]<mincost[s]))s=u;//第一个存的是第一个点，在这里是顶点0
        }
        if(s==-1)break;//代表已经找不到能加入集合x的点了
        used[s]=true;//把s放入集合x中
        res+=mincost[s];
        for(int u=0;u<v;u++)
        {
            mincost[u]=min(mincost[u],cost[s][u]);//把图看懂就ok
        }
    }
    return res;
}

//kruskal算法    o（n*logn）  算了贴博客吧，，主要因为这个算法made还要用并查集，我特么懒得找并查集板子套了
struct edge{
 int u,v,cost;
};
bool comp(const edge&)