Kruskal模板

struct edge
{
    int u,v,cost;
}eg[50010];
int par[1010],high[1010];
bool cmp(edge x,edge y)
{
    return x.cost<y.cost;
}
void init(int n)
{
    for(int i=1;i<=n;i++)
    {
        par[i]=i;
        high[i]=0;
    }
}
int find(int x)
{
    if(par[x]==x)return x;
    return par[x]=find(par[x]);
}
void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)return;
    if(high[x]<high[y])par[x]=y;
    else
    {
        par[y]=x;
        if(high[x]==high[y])high[x]++;
    }
}
bool same(int x,int y)
{
    return find(x)==find(y);
}
int main()
{
    int n,m,i,sum,num;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++)
        scanf("%d%d%d",&eg[i].u,&eg[i].v,&eg[i].cost);
    sort(eg,eg+m,cmp);
    init(n);
    sum=0;num=0;
    for(i=0;i<m;i++)
    {
        if(!same(eg[i].u,eg[i].v))
        {
            unite(eg[i].u,eg[i].v);
            sum=sum+eg[i].cost;
            num++;
        }
        if(num==n-1)break;
    }
    printf("%d\n",sum);
    return 0;
}

Prim优化模板

http://www.cnblogs.com/yspworld/p/4546098.html

struct edge
{
    int to,cost;
};
struct cmp
{
    bool operator()(edge x,edge y)
    {
        return x.cost>y.cost;
    }
};
vector<edge>v[1010];
bool vis[1010];
int n;
void prim()
{
    int ans=0,cnt=n-1;
    fill(vis+1,vis+1+n,false);
    priority_queue<edge,vector<edge>,cmp> q;
    for(int i=0;i<v[1].size();i++)
        q.push(v[1][i]);   //将起点的所有连接边全部加入队列中来
    vis[1]=true;
    while(!q.empty()&&cnt)
    {
        edge e=q.top();
        q.pop();
        if(vis[e.to])continue;
        ans=ans+e.cost;
        cnt--;
        vis[e.to]=true;
        for(int i=0;i<v[e.to].size();i++)
            if(!vis[v[e.to][i].to])
                q.push(v[e.to][i]);
    }
    printf("%d\n",ans);
}
int main()
{
    int n,m,i,a,b,c;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        v[i].clear();
    for(i=0;i<m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        v[a].push_back(edge{b,c});
        v[b].push_back(edge{a,c});
    }
    prim();
    return 0;
}

POJ 2421

题意：

​ 已经给了一些路，然后让你求其余的。

解题思路：

​ 用kruskal的时候要注意给出的边是不是成环的，还是得判断一下。

POJ 1679

题意：

​ 给一个有权值的无向图，判断最小生成树是否唯一。

解题思路：

​ 求一下次小生成树即可。这里要注意每次生成一个次小生成树的时候要判断是否成功生成。

ZOJ 1586

题意：

​ 在某个外星球有些叫QS的外星人。他们之间要相互联系。但是要买网络适配器，当然不同的QS喜欢不同价格的适配器。而且还需要买网络电缆，而且都需要费用。让你求用最小的花费去建立他们之间的联系。

解题思路：

​ 注意不能之后再加适配器的价格，因为这样的话考虑最短路的时候就没有把适配器的价格考虑进去了。