PTA 7-1 畅通工程之局部最小花费问题(35 分)

7-1 畅通工程之局部最小花费问题(35 分)

某地区经过对城镇交通状况的调查,得到现有城镇间快速道路的统计数据,并提出“畅通工程”的目标:使整个地区任何两个城镇间都可以实现快速交通(但不一定有直接的快速道路相连,只要互相间接通过快速路可达即可)。现得到城镇道路统计表,表中列出了任意两城镇间修建快速路的费用,以及该道路是否已经修通的状态。现请你编写程序,计算出全地区畅通需要的最低成本。

输入格式:

输入的第一行给出村庄数目N (1≤N≤100);随后的N(N−1)/2行对应村庄间道路的成本及修建状态:每行给出4个正整数,分别是两个村庄的编号(从1编号到N),此两村庄间道路的成本,以及修建状态 — 1表示已建,0表示未建。

输出格式:

输出全省畅通需要的最低成本。

输入样例:

4
1 2 1 1
1 3 4 0
1 4 1 1
2 3 3 0
2 4 2 1
3 4 5 0

输出样例:

3普里姆算法
#include<iostream>
#include<fstream>
using  namespace std;
#define INF 0x3f3f3f3f
const int maxn = 117;
int m[maxn][maxn];
int vis[maxn], low[maxn];
int n;
int prim()
{
    vis[1] = 1;
    int sum = 0;
    int pos, minn;
    pos = 1;
    for(int i = 1; i <= n; i++)
    {
        low[i] = m[pos][i];
    }
    for(int i = 1; i < n; i++)
    {
        minn = INF;
        for(int j = 1; j <= n; j++)
        {
            if(!vis[j] && minn > low[j])
            {
                minn = low[j];
                pos = j;
            }
        }
        sum += minn;
        vis[pos] = 1;
        for(int j = 1; j <= n; j++)
        {
            if(!vis[j] && low[j] > m[pos][j])
            {
                low[j] = m[pos][j];
            }
        }
    }
    return sum;
}

int main()
{
    scanf("%d",&n);
    int ms = n*(n-1)/2;
    int x,y,cost,tes;
    for(int i = 1; i <= n ;i++ )
        for(int j = 1; j <= n; j++)
        m[i][j] = INF;
    for(int i = 1; i <= ms ; i++)
    {
        cin>>x>>y>>cost>>tes;
        m[x][y] = m[y][x] = tes==1?0:cost;
    }
    cost = prim();
    cout<< cost << endl;
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

HDU 1847 Good Luck in CET-4 Everybody!(规律,博弈)

Good Luck in CET-4 Everybody! Time Limit: 1000/1000 MS (Java/Others)    Memory L...

2718
来自专栏大数据文摘

手把手|如何用Python绘制JS地图?

42613
来自专栏有趣的Python

TensorFlow应用实战-6-AI作曲环境搭建读作sharp,是音乐里的升音符号,在sharp前面的这个音去升高一个半音。

用TensorFlow开发会作曲的AI 背景和知识点介绍 人工智能的不断火热。 Google的Magenta(洋红色)项目 ? mark https://mag...

4519
来自专栏生信技能树

dbSNFP数据库发展历程

1795
来自专栏数据结构与算法

CDQZ 0003:jubeeeeeat

总时间限制: 1000ms 内存限制: 256000kB描述 众所周知,LZF很喜欢打一个叫Jubeat的游戏。这是个音乐游戏,游戏界面是4×4的方阵,会根...

3196
来自专栏数据魔术师

干货 | 变邻域搜索算法(VNS)求解TSP(附C++详细代码及注释)

上次变邻域搜索的推文发出来以后,看过的小伙伴纷纷叫好。小编大受鼓舞,连夜赶工,总算是完成了手头上的一份关于变邻域搜索算法解TSP问题的代码。今天,就在此...

7552
来自专栏数据结构与算法

HDU 1847 Good Luck in CET-4 Everybody!(找规律版巴什博奕)

Problem Description 大学英语四级考试就要来临了,你是不是在紧张的复习?也许紧张得连短学期的ACM都没工夫练习了,反正我知道的Kiki和...

3558
来自专栏大数据挖掘DT机器学习

用pandas 进行投资分析

让我们进行一个常见的分析,您可能自己就可以完成这个分析。假设您想分析股票绩效,那么您可以: 在 Yahoo 金融专区找一支股票。 下载历史数据,保存为 CSV ...

2895
来自专栏数据小魔方

动态地理信息可视化——leaflet在线地图简介

最近稍微涉猎了一下leaflet这个包,突然感到发现了动态可视化的新大门,这个包所提供的地图类型、动态效果、图层展示方式都大大扩展了ggplot作图系统的在数据...

3644
来自专栏专知

【论文推荐】最新六篇聊天机器人相关论文—弱监督信息、内容驱动、对话管理系统、可扩展情感序列到序列、自主性

2032

扫码关注云+社区