POJ 1258 Agri-Net(最小生成树 Prim+Kruskal)

时间:2023-01-06 21:42:17

题目链接: 传送门

Agri-Net

Time Limit: 1000MS     Memory Limit: 10000K

Description

Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course.
Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms.
Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm.
The distance between any two farms will not exceed 100,000.

Input

The input includes several cases. For each case, the first line contains the number of farms, N (3 <= N <= 100). The following lines contain the N x N conectivity matrix, where each element shows the distance from on farm to another. Logically, they are N lines of N space-separated integers. Physically, they are limited in length to 80 characters, so some lines continue onto others. Of course, the diagonal will be 0, since the distance from farm i to itself is not interesting for this problem.

Output

For each case, output a single integer length that is the sum of the minimum length of fiber required to connect the entire set of farms.

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;
}

POJ 1258 Agri-Net(最小生成树 Prim+Kruskal)的更多相关文章

  1. 最小生成树 Prim Kruskal

    layout: post title: 最小生成树 Prim Kruskal date: 2017-04-29 tag: 数据结构和算法 --- 目录 TOC {:toc} 最小生成树Minimum ...

  2. 邻接矩阵c源码(构造邻接矩阵,深度优先遍历,广度优先遍历,最小生成树prim&comma;kruskal算法)

    matrix.c #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include < ...

  3. 数据结构学习笔记05图&lpar;最小生成树 Prim Kruskal&rpar;

    最小生成树Minimum Spanning Tree 一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边. 树: 无回路   |V|个顶 ...

  4. 布线问题 最小生成树 prim &plus; kruskal

    1 : 第一种 prime     首先确定一个点 作为已经确定的集合 , 然后以这个点为中心 , 向没有被收录的点 , 找最短距离( 到已经确定的点 ) , 找一个已知长度的最小长度的 边 加到 s ...

  5. POJ 1258 Agri-Net(最小生成树,模板题)

    用的是prim算法. 我用vector数组,每次求最小的dis时,不需要遍历所有的点,只需要遍历之前加入到vector数组中的点(即dis[v]!=INF的点).但其实时间也差不多,和遍历所有的点的方 ...

  6. POJ 1258 Agri-Net (最小生成树)

    Agri-Net 题目链接: http://acm.hust.edu.cn/vjudge/contest/124434#problem/H Description Farmer John has be ...

  7. POJ 1751 Highways(最小生成树&amp&semi;Prim)题解

    思路: 一开始用Kruskal超时了,因为这是一个稠密图,边的数量最惨可能N^2,改用Prim. Prim是这样的,先选一个点(这里选1)作为集合A的起始元素,然后其他点为集合B的元素,我们要做的就是 ...

  8. 最小生成树-Prim&amp&semi;Kruskal

    Prim算法 算法步骤 S:当前已经在联通块中的所有点的集合 1. dist[i] = inf 2. for n 次 t<-S外离S最近的点 利用t更新S外点到S的距离 st[t] = true ...

  9. 邻接表c源码(构造邻接矩阵,深度优先遍历,广度优先遍历,最小生成树prim&comma;kruskal算法)

    graph.c #include <stdio.h> #include <stdlib.h> #include <limits.h> #include " ...

随机推荐

  1. http服务的安装与配置

    挂载光盘mount /dev/cdrom /y       #y是挂载光盘的位置 使用yum命令进安装httpd服务 yum命令的配置文件, yum配置文件位于 /etc/yun.repos.d 目录 ...

  2. Java---Java的面试题(一)

    1.什么是Java虚拟机?为什么Java被称作是"平台无关的编程语言"? Java虚拟机是一个可以执行Java字节码的虚拟机进程.Java源文件被编译成能被Java虚拟机执行的字节 ...

  3. JavaScript之继承(原型链)

    JavaScript之继承(原型链) 我们知道继承是oo语言中不可缺少的一部分,对于JavaScript也是如此.一般的继承有两种方式:其一,接口继承,只继承方法的签名:其二,实现继承,继承实际的方法 ...

  4. android studio新项目时提示:Plugin is too old&comma; please update to a more recent version

    今天想写一个程序来测试一下android studo代码,但是创建好项目后,提示: Error:(1, 0) Plugin is too old, please update to a more re ...

  5. 关于AuthorizeAttribute使用

    在开发中,假如你只对一个角色进行权限处理,你可以这么写 class ActionAuthAttribute : AuthorizeAttribute { private RoleType _roleT ...

  6. 判断直线与线段相交 POJ 3304 Segments

    题意:在二维平面中,给定一些线段,然后判断在某直线上的投影是否有公共点. 转化,既然是投影,那么就是求是否存在一条直线L和所有的线段都相交. 证明: 下面给出具体的分析:先考虑一个特殊的情况,即n=1 ...

  7. swift论坛正式上线

    www.iswifting.com swift论坛正式上线.有问答专区,也有技术分享区,还有学习资料区,大家一起学习成长! 2014中国互联网大会于8月26日开幕. *主管部门.行业专家.企业领袖将 ...

  8. mshcMigrate制作的mshc文件中有链接打不开

    网上下载的c3ddotnetapiref.chm文件, 使用mshcMigrate工具(2.0.0.75)转换成mshc文件, 添加到help viewer 2.2中, 有时会遇到这样的错误: 选择是 ...

  9. 微星X470主板装机

    记录一下装机过程,以作纪念 配置 机箱:先马黑洞3 电源:先马金牌500w CPU:AMD 锐龙5:2600X 主板:微星 X470 暗黑版 显卡:七彩虹 RTX2060 内存:科赋 3200,2条8 ...

  10. 八&period;nginx网站服务实践应用

    期中集群架构-第八章-期中架构nginx章节====================================================================== 01. web ...