PTA 数据结构畅通工程之局部最小花费问题

深藏阁楼爱情的钟 2022-05-15 14:19 98阅读 0赞

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

### 输出样例: ###

思路：将已建好的路价格设为0，然后用kruscal求最小生成树。

#include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #define INFINITY 0x3f3f3f3f
    using namespace std;
    typedef struct 
    {
        int villageA;
        int villageB;
        int price;
        bool status;
    }Node;
    Node road[6000];
    int flag[6000];
    int UnionFindNode[6000]; //并查集每个节点
    int high[6000]; //树的高度
     
    //初始化n个节点
    void Init(int n)
    {
        for(int i = 1; i <= n; i++)
        {
            UnionFindNode[i] = i;
            high[i] = 1;
        }
    }
    //查找当前元素所在树的根节点(代表元素)
    int find(int x)
    {
        if(x == UnionFindNode[x])
           return x;
        return UnionFindNode[x] = find(UnionFindNode[x]); //在第一次查找时，将节点直连到根节点
    }
    
    //合并元素x， y所处的集合
    void Unite(int x, int y)
    {
        //查找到x，y的根节点
        x = find(x);
        y = find(y);
        if(x == y) 
            return ;
        //判断两棵树的高度，然后在决定谁为子树
        if(high[x] < high[y])
        {
            UnionFindNode[x] = y;
        }
        else
        {
            UnionFindNode[y] = x;
            if(high[x] == high[y]) 
            high[x]++;
        }
    }
    //判断x，y是属于同一个集合
    bool same(int x, int y)
    {
        return find(x) == find(y);
    }
    int findmin(int n)
    {
        int min = INFINITY;
        int indexofmin = INFINITY;
        for(int i=0;i<n;i++)
        {
            if(road[i].price < min && !flag[i])
            {
                min = road[i].price;
                indexofmin = i;
            }
        }
        flag[indexofmin] = 1;
        return indexofmin;
    }
    
    int KrusKal(int n)
    {  
        int SumMoney = 0;
        for(int i=0;i<n;i++)
        {
            int index = findmin(n);
            if(!same(road[index].villageA,road[index].villageB))
            {
                Unite(road[index].villageA,road[index].villageB);
                SumMoney += road[index].price;
            }
        }
        return SumMoney;
    }
    int main()
    {
        memset(flag,0,sizeof(flag));
        int N;
        cin>>N;
        int n = N*(N-1)/2;
        Init(N);
        for(int i=0;i<n;i++)
        {   
            cin>>road[i].villageA>>road[i].villageB>>road[i].price>>road[i].status;
            if(road[i].status)
                road[i].price = 0;
        }
        int MinMoney = KrusKal(n);
        cout<<MinMoney<<endl;
        return 0;
    }