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 条评论
登录 后参与评论

相关文章

来自专栏iOSDevLog

ARKit和CoreLocation:第一部分

演示代码 ARKit和CoreLocation:第一部分 ARKit和CoreLocation:第二部分 ARKit和CoreLocation:第三部分

29620
来自专栏大数据文摘

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

562130
来自专栏利炳根的专栏

学习笔记CB003:分块、标记、关系抽取、文法特征结构

分块,根据句子的词和词性,按照规则组织合分块,分块代表实体。常见实体,组织、人员、地点、日期、时间。名词短语分块(NP-chunking),通过词性标记、规则识...

23190
来自专栏机器之心

资源 | 囊括欧亚非大陆多种语言的25个平行语料库数据集(拿走不谢!)

原文链接:https://gengo.ai/datasets/25-best-parallel-text-datasets-for-machine-transl...

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

用R语言对城管事件数据分析

作者:夏尔康 https://ask.hellobi.com/blog/xiaerkang/3975 这次使用主成分分析主要目的并不是降维,而是分析城管数据中的...

34990
来自专栏生信技能树

【直播】我的基因组55:简单的PCA分析千人基因组的人群分布

好久不见,我们的直播又开始啦!今天,我们主要讲的是人群分布,先用简单的PCA来分析一下千人基因组的人群分布吧! PCA分析,就是主成分分析,我博客有讲过(点击最...

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

快速数论变换(NTT)小结

在FFT中,我们需要用到复数,复数虽然很神奇,但是它也有自己的局限性——需要用double类型计算,精度太低

51380
来自专栏小樱的经验随笔

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

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

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

用pandas 进行投资分析

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

30950
来自专栏量化投资与机器学习

【高能】用PyMC3进行贝叶斯统计分析(代码+实例)

问题类型1:参数估计 真实值是否等于X? 给出数据,对于参数,可能的值的概率分布是多少? 例子1:抛硬币问题 硬币扔了n次,正面朝上是h次。 参数问题 想知道...

1.1K100

扫码关注云+社区

领取腾讯云代金券