POJ 1258 Agri-Net（最小生成树 Prim+Kruskal）

题目链接: 传送门

Agri-Net

Time Limit: 1000MS     Memory Limit: 10000K

Description

Input

Output

Sample Input

4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

Sample Output

28

Prim算法O（V^2)

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX_V = 105;
int edge[MAX_V][MAX_V];
int dis[MAX_V];
bool vis[MAX_V];
int N;

int prim()
{
    memset(dis,INF,sizeof(dis));
    memset(vis,false,sizeof(vis));
    for (int i = 1;i <= N;i++)
    {
        dis[i] = edge[i][1];
    }
    dis[1] = 0;
    vis[1] = true;
    int sum = 0;
    for (int i = 1;i < N;i++)
    {
        int tmp = INF,pos;
        for (int j = 1;j <= N;j++)
        {
            if(!vis[j] && tmp > dis[j])
            {
                tmp = dis[j];
                pos = j;
            }
        }
        if (tmp == INF) return 0;
        vis[pos] = true;
        sum += dis[pos];
        for(int j = 1;j <= N;j++)
        {
            if (!vis[j] && edge[pos][j] < dis[j])
            {
                dis[j] = edge[pos][j];
            }
        }
    }
    return sum;
}

int main()
{
    while (~scanf("%d",&N))
    {
        for (int i = 1;i <= N;i++)
        {
            for (int j = 1;j <= N;j++)
            {
                scanf("%d",&edge[i][j]);
            }
        }
        int res = prim();
        printf("%d\n",res);
    }
    return 0;
}

Prim算法O(ElogV)

#include<iostream>
#include<vector>
#include<queue>
#include<utility>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef __int64 LL;
typedef pair<int,int>pii;  //first  最短距离  second 顶点编号
const int INF = 0x3f3f3f3f;
const int MAX = 105;
struct edge{
    int to,cost;
    edge(int t,int c):to(t),cost(c){}
};
vector<edge>G[MAX];
int N,dis[MAX];
bool vis[MAX];

int prim()
{
    int res = 0;
    priority_queue<pii,vector<pii>,greater<pii> >que;
    memset(dis,INF,sizeof(dis));
    memset(vis,false,sizeof(vis));
    dis[1] = 0;
    que.push(pii(0,1));
    while (!que.empty())
    {
        pii p = que.top();
        que.pop();
        int v = p.second;
        if (vis[v] || p.first > dis[v]) continue;
        vis[v] = true;
        res += dis[v];
        for (int i = 0;i < G[v].size();i++)
        {
            edge e = G[v][i];
            if (dis[e.to] >  e.cost)
            {
                dis[e.to] = e.cost;
                que.push(pii(dis[e.to],e.to));
            }
        }

    }
    return res;
}

int main()
{
    while (~scanf("%d",&N))
    {
        int tmp;
        for (int i = 1;i <= N;i++)
        {
            G[i].clear();
            for (int j = 1;j <= N;j++)
            {
                scanf("%d",&tmp);
                G[i].push_back(edge(j,tmp));
            }
        }
        int res = prim();
        printf("%d\n",res);
    }
    return 0;
}

Kruskal算法O（ElogV）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX = (105*105-105)/2;
struct Edge{
    int u,v,w;
};
int N,father[MAX],rk[MAX];
struct Edge edge[MAX];

bool cmp(Edge x,Edge y)
{
    return x.w < y.w;
}

void init()
{
    memset(father,0,sizeof(father));
    memset(rk,0,sizeof(rk));
    for (int i = 0;i <= N;i++)
    {
        father[i] = i;
    }
}

int find(int x)
{
    int r = x;
    while (father[r] != r)
    {
        r = father[r];
    }
    int i = x,j;
    while (i != r)
    {
        j = father[i];
        father[i] = r;
        i = j;
    }
    return r;
}
/*int find(int x)
{
    return x == father[x]?x:father[x] = find(father[x]);
}*/

void unite(int x,int y)
{
    int fx,fy;
    fx = find(x);
    fy = find(y);
    if (fx == fy)   return;
        if (rk[fx] < rk[fy])
        {
            father[fx] = fy;
        }
        else
        {
            father[fy] = fx;
            if (rk[x] == rk[y])
            {
                rk[x]++;
            }
        }

}

/*void unite(int x,int y)
{
    int fx = find(x),fy = find(y);
    if (fx != fy)
    {
        father[fx] = fy;
    }
}*/

int main()
{
    while (~scanf("%d",&N))
    {
        int tmp,cnt = 0,sum = 0;
        for (int i = 1;i <= N;i++)
        {
            for (int j = 1;j <= N;j++)
            {
                scanf("%d",&tmp);
                if (i < j)
                {
                    edge[cnt].u = i;
                    edge[cnt].v = j;
                    edge[cnt].w = tmp;
                    cnt++;
                }
            }
        }
        init();
        sort(edge,edge+cnt,cmp);
        for (int i = 0;i < cnt;i++)
        {
            int x,y;
            x = find(edge[i].u);
            y = find(edge[i].v);
            if (x != y)
            {
                unite(x,y);
                sum += edge[i].w;
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}