专栏首页算法与数据结构PTA 7-1 畅通工程之局部最小花费问题(35 分)

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 - 5695

    众所周知,度度熊喜欢各类体育活动。  今天,它终于当上了梦寐以求的体育课老师。第一次课上,它发现一个有趣的事情。在上课之前,所有同学要排成一列, 假设最开始每...

    Kindear
  • 数据结构 图

    1-1 无向连通图至少有一个顶点的度为1 错误: 无向连通图考点: 1. 每条边连接两个顶点,所有顶点的度之和等于边数的2倍 2.记住两个特殊的无相连通图模型:...

    Kindear
  • 吉林大学考研复试题目(牛客网)

    ​ 一个二进制数,将其每一位取反,称之为这个数的反码。下面我们定义一个字符的反码。如果这是一个小写字符,则它和字符'a’的距离与它的反码和字符'z’的距离相同;...

    Kindear
  • 计蒜客2018 蓝桥杯省赛 B 组模拟赛(一)

    Zoctopus
  • POJ Test for Job(DAG上拓扑排序)

           题意是给了n个点,m条边(单向边),然后每个点都有一个点权(存在负权),问从入度为0的点开始到出度为0的点,最大的权值和为多少。

    Ch_Zaqdt
  • 15.瀑布流、测量

    六月的雨
  • 初级程序员面试不靠谱指南(三)

    二、指针的好基友的& 1.&的意义。说&是指针的好基友其实不恰当,因为&这个符号在C/C++不止有一种含义,但是因为其经常会和指针一起出现在被问的问题列表上,所...

    一心一怿
  • 1250 Fibonacci数列

    时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果 题目描述 Description 定义:f0=...

    attack
  • 剑指Offer-构建乘积数组

    package Array; import sun.security.util.Length; /** * 构建乘积数组 * 给定一个数组A[0,1,....

    武培轩
  • 「CodeForces - 598B」Queries on a String

    字符串s(1 ≤ |s| ≤ 10 000),有m(1 ≤ m ≤ 300)次操作,每次给l,r,k,代表将r位置插入l位置前,执行k(1 ≤ k ≤ 1 00...

    饶文津

扫码关注云+社区

领取腾讯云代金券