Prim-NYOJ-38-配線の問題
配線問題時間制限: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;
}