学步园

Prim。

#include <stdio.h>
#include <string.h>

#define CLR(a,v) memset(a,v,sizeof(a))
#define min(a,b) a < b ? a : b

#define N 105
#define M 10005

struct Vertex
{
	int head;
}V[N];

struct Edge
{
	int v,w,next;
}E[M];

int n,m,top,d[N];

void Init()
{
	CLR(d,127);
	CLR(V,-1);
	top = 0;
}

void Add_Edge(int u,int v,int w)
{
	E[top].v = v;
	E[top].w = w;
	E[top].next = V[u].head;
	V[u].head = top++;
}

int Prim()
{
    if(n == 1)
        return 0;
	int ans = 0, p = 1,t = n-1;
	d[1] = d[0]+1;
	do
	{
		for(int i=V[p].head;i!=-1;i=E[i].next)
		{
			int q = E[i].v;
			if(d[q] <= d[0])
                d[q] = min(d[q],E[i].w);
		}
		int mmin = d[0];
		for(int i=2;i<=n;i++)
			if(d[i] < mmin)
				mmin = d[i],p = i;
        if(mmin == d[0])
            return -1;
        d[p] = d[0]+1;
		ans += mmin;
	}while(--t);
	return ans;
}

Prim 优先队列。

#include <queue>
#include <stdio.h>
#include <string.h>

using namespace std;

#define CLR(a,v) memset(a,v,sizeof(a))
#define min(a,b) a < b ? a : b

#define N 105
#define M 10005

struct Vertex
{
	int head;
}V[N];

struct Edge
{
	int v,w,next;
}E[M];

struct Node
{
    Node(int u,int w):u(u),w(w){}
    int u,w;
    bool operator < (const Node& S)const
	{
	    return w > S.w;
	}
};

int n,m,top,d[N];

bool in[N];

void Init()
{
	CLR(in,false);
	CLR(d,127);
	CLR(V,-1);
	top = 0;
}

void Add_Edge(int u,int v,int w)
{
	E[top].v = v;
	E[top].w = w;
	E[top].next = V[u].head;
	V[u].head = top++;
}

int Prim()
{
	int ans = 0 ,t = n;
	priority_queue<Node> Q;
	d[1] = 0;
	Q.push(Node(1,0));
	while(!Q.empty())
	{
	    Node R = Q.top();Q.pop();
	    int p = R.u;
	    if(in[p])
            continue;
        in[p] = true;
        ans += R.w;
        --t;
		for(int i=V[p].head;i!=-1;i=E[i].next)
		{
			int q = E[i].v;
			if(!in[q] && E[i].w < d[q])
			{
			    d[q] = E[i].w;
			    Q.push(Node(q,E[i].w));
			}
		}
	}
	return t ? -1 : ans;
}

Kruskal。

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

#define CLR(a,v) memset(a,v,sizeof(a))

#define N 105
#define M 10005

struct Edge
{
	int u,v,w;
	bool operator < (const Edge& S)const
	{
	    return w < S.w;
	}
}E[M];

int n,m,pre[N];

void Init()
{
    CLR(pre,-1);
}

int Root(int x)
{
    if(pre[x] != -1)
        return pre[x] = Root(pre[x]);
    else
        return x;
}

bool Union(int a,int b)
{
    int r1 = Root(a);
    int r2 = Root(b);
    if(r1 == r2)
        return true;
    pre[r1] = r2;
    return false;
}

int Kruscal()
{
	int ans = 0, t = n-1;
	for(int i=0;t && i<m;i++)
	{
	    if(Union(E[i].u,E[i].v))
            continue;
		ans += E[i].w;
		--t;
	}
	return t ? -1 : ans;
}