引水工程(最小生成树)

Minimum Spanning Tree

Posted by Scalpel on March 22, 2016

题目链接

题意:

有N个区域需要建设水资源工程,可以自建水库解决缺水,也可以从已有水源的地区建立管道引水,给出自建水库的费用和相互引水的费用,求工程的最小花费。

思路**:

最小生成树的模板题,稠密图,可以用Prim算法。以引水的费用作为边权,找到自建费用最低的区域,以它为根,通过比较自建和引水的最小值来不断生成树。

#include <iostream>
#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 300;

#define FIO ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define FILEREAD freopen("input.txt", "r", stdin);

int G[N][N], lowcost[N], cost[N];
bool used[N];

int prim(int vcount, int minv)
{
    int sum = 0;
    for (int i = 0; i < vcount; i++)
    {
        lowcost[i] = min(G[minv][i], cost[i]);
        used[i] = false;
    }
    used[minv] = true;
    for (int i = 1; i <= vcount - 1; i++)
    {
        int j = 0, mincost = INF;
        for (int k = 0; k < vcount; k++)
            if ((!used[k]) && (lowcost[k] < mincost))
            {
                mincost = lowcost[k];
                j = k;
            }
        used[j] = true;
        sum += mincost;
        for (int k = 0; k < vcount; k++)
            if (!used[k] && (min(cost[k], G[j][k]) < lowcost[k]))
                lowcost[k] = min(cost[k], G[j][k]);
    }
    return sum;
}

int main()
{
    #ifndef ONLINE_JUDGE
        FILEREAD
    #endif
    FIO
    int k;
    cin >> k;
    while(k--)
    {
        int n;
        cin >> n;
        int minv = 0;
        for (int i = 0; i < n; ++i)
        {
            cin >> cost[i];
            if (cost[minv] > cost[i])
                minv = i;
        }
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                cin >> G[i][j];
        cout << prim(n, minv) + cost[minv] << endl;
    }
    return 0;
}