【BNUOJ】電網建設(MST，prim)

題目連結：

http://acm.bnu.edu.cn/v3/problem_show.php?pid=1056

分析：

每個節點可以選擇建電廠或者與其他電廠連接配接。我們可以虛拟出一個節點，這個節點連接配接所有其他節點ai，且邊權為在ai建電廠花費的費用；

這樣，初始化時，就可以直接把dis[i]初始化為在i處建電廠的費用。然後用prim處理即可。

代碼：

#include <cstdio>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#define LL long long
#define db double
#define pi acos(-1.0)
#define pr printf
#define sc scanf
#define mod
#define N 310
using namespace std;
LL MAX_LL = 0xfffffffffffffffLL;

int dis[N];
int c[N][N];
bool vis[N];

void Init(int n)
{
    int i;
    for(i=0;i<n;++i)
    {
        vis[i] = 0;
    }
}

int main()
{
    int n,m,i,j,minn,now,sum;
    while(sc("%d",&n)+1&&n)
    {
        Init(n);

        for(i=0;i<n;++i)
            sc("%d",&dis[i]);
        for(i=0;i<n;++i)
            for(j=0;j<n;++j)
                sc("%d",&c[i][j]);

        for(i=0;i<n;++i)
        {
            minn =INT_MAX;
            for(j=0;j<n;++j)
            {
                if(dis[j]<minn&&!vis[j])
                {
                    minn = dis[j];
                    now = j;
                }
            }
            vis[now] = 1;
            for(j=0;j<n;++j)
            {
                if(!vis[j]&&c[now][j]<dis[j])
                    dis[j] = c[now][j];
            }

        }
        sum = 0;
        for(i=0;i<n;++i)
            sum+=dis[i];
        pr("%d\n",sum);
    }

    return 0;
}