Prim-NYOJ-38-配線の問題

6347 ワード

配線問題時間制限:1000 ms|メモリ制限:65535 KB難易度:4南陽理工学院が電気回線の改造を行うことを説明し、現在校長はデザイナーに以下の条件を満たす配線方式を設計するように要求した.2、使用する電線の最低入力第1行は整数nであり、n組のテストデータがあることを示す.(n<5)各試験データの最初の行は2つの整数vであり、e.vは学校の建物の総個数(v<=500)の後のe行を表し、各行には3つの整数aがあり、b,cはaとbの間に敷設線路を建設するのにc(c<=100)がかかることを示す.(どの2棟の間に費用が明記されていない場合は、この2棟が直接連通するのに費用がかかりすぎるか、連通不可能であることを示す)その後の1行には、i番目の数がi番目のビルの配線から外部の電力供給施設への費用を表すv個の整数がある.(0問題解:問題の中であなたに1本の最小生成木ですべてのビルをつなぎ合わせて、それからまたそれぞれのビルに1つの重み値をあげて、1つの重み値の最小のビルの最もルートを探せばいいです.直接primの後にMSTで1つの最も小さいビルの権利値をプラスして出力します.
//
// main.cpp
// NYOJ-38-    
//
// Created by     on 15/11/25.
// Copyright © 2015     . All rights reserved.
//
// 52ms 1252KB

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <stdlib.h>

#define MAXS 0x7fffffff
using namespace std;

const int MAXN=510;
bool vis[MAXN];
long long int lowc[MAXN];
int cost[MAXN][MAXN];
long long int Prim(long long int n)
{
    long long int ans=0;
    memset(vis, 0, sizeof(vis));
    vis[0]=1;
    for (int i=1; i<n; i++)
        lowc[i]=cost[0][i];
    for (int i=1; i<n; i++) {
        long long int minc=MAXS;
        int p=-1;
        for (int j=0; j<n; j++)
            if (!vis[j] && minc>lowc[j]) {
                minc=lowc[j];
                p=j;
            }
        if (minc == MAXS)
            return -1;
        ans+=minc;
        vis[p]=1;
        for (int j=0; j<n; j++) {
            if (!vis[j] && lowc[j]>cost[p][j])
                lowc[j]=cost[p][j];
        }
    }
    return ans;
}



int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    while (n--) {
        int v,e,a,b,c;
        cin >> v >> e;
        for (int i=0; i<v; i++) {
            for (int j=0; j<v; j++) {
                if (i==j) {
                    cost[i][j]=0;
                }
                else
                    cost[i][j]=MAXS;
            }
        }
        for (int i=1; i<=e; i++) {
            scanf("%d %d %d",&a,&b,&c);
            cost[a-1][b-1]=min(cost[a-1][b-1],c);
            cost[b-1][a-1]=min(cost[b-1][a-1],c);
        }
        long long int sum=Prim(v);
        int temp=MAXS;
        for (int i=1; i<=v; i++) {
            scanf("%d",&a);
            temp=min(temp,a);
        }
        sum+=temp;
        cout << sum << endl;
    }
    return 0;
}