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

相关文章

来自专栏数据结构与算法

洛谷P2052 [NOI2011]道路修建(树形DP)

在 W 星球上有 n 个国家。为了各自国家的经济发展,他们决定在各个国家 之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬,他们只愿 意修建恰好 n...

954
来自专栏HansBug's Lab

2429: [HAOI2006]聪明的猴子

2429: [HAOI2006]聪明的猴子 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 448  Sol...

28412
来自专栏ml

nyoj------20吝啬的国度

吝啬的国度 时间限制:1000 ms  |  内存限制:65535 KB 难度:3  描述在一个吝啬的国度里有N个城市,这N个城市间只有N-1条路把这个N个城市...

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

P1007 独木桥

题目背景 战争已经进入到紧要时间。你是运输小队长,正在率领运输部队向前线运送物资。运输任务像做题一样的无聊。你希望找些刺激,于是命令你的士兵们到前方的一座独木桥...

2588
来自专栏C语言及其他语言

【每日一题】问题 1650[蓝桥杯][算法训练VIP]猴子分苹果

题目描述 秋天到了,n只猴子采摘了一大堆苹果放到山洞里,约定第二天平分。这些猴子很崇拜猴王孙悟空,所以都想给他留一些苹果。第一只猴子悄悄来到山洞,把苹果平均...

3488
来自专栏wym

HDU 4925 Apple Tree(规律 构造)

题目:http://acm.hdu.edu.cn/showproblem.php?pid=4925

452
来自专栏ml

hdu-----(4514)湫湫系列故事——设计风景线(树形DP+并查集)

湫湫系列故事——设计风景线 Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65535/3276...

3648
来自专栏WOLFRAM

Mathematica 迷中智 | 奥运五环 数字谜题

1372
来自专栏专知

关关的刷题日记90 – Leetcode 400. Nth Digit

关关的刷题日记90 – Leetcode 400. Nth Digit 题目 Find the nth digit of the infinite intege...

3675
来自专栏青青天空树

挖掘机技术哪家强(c++实现)

描述:为了用事实说明挖掘机技术到底哪家强,组织一场挖掘机技能大赛。现请你根据比赛结果统计出技术最强的那个学校。

571

扫码关注云+社区