백준 10423번 : 전기가 부족해

문제 링크

약간 변형된 MST문제였습니다.

각 도시는 어떤 발전소에서 전기를 공급받아도 상관이 없고, 한개에서만 공급받으면 됩니다.

또한, 발전소 자체에서는 전기가 공급이 가능합니다.

따라서 Union-Find자료구조를 이용하여 크루스칼 알고리즘을 통해 해결하였습니다.

먼저 발전소들을 merge함수를 이용하여 묶어준 후, 그 이후에는 일반적인 크루스칼 알고리즘을 이용하여 구현했습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>

using namespace std;

typedef pair<int,int> pii;

struct Edge{
	int v1,v2,w;
	
	Edge(int _v1,int _v2,int _w):v1(_v1),v2(_v2),w(_w)
	{	}
	
	bool operator<(const Edge& rhs) const
	{
		return w < rhs.w;
	}
};

vector<int> p;
vector<Edge> edg;

int find(int a)
{
	if(p[a] != a) p[a] = find(p[a]);
	return p[a];
}

bool merge(int u,int v)
{
	u = find(u);
	v = find(v);
	
	if(u == v) return false;
	
	p[u] = v;
	
	return false;
}

int n,m,k;

int main(int argc, char** argv) {
	
	scanf("%d %d %d",&n,&m,&k);
	
	for(int i = 0;i<n;i++)
	{
		p.push_back(i);
	}
	
	vector<int> plant;
	for(int i = 0;i<k;i++)
	{
		int plt;
		scanf("%d",&plt);
		
		plt--;
			
		plant.push_back(plt);
	}
	
	for(int i = 1;i<k;i++)
	{
		merge(plant[i-1],plant[i]);
	}
	
	
	for(int i = 0;i<m;i++)
	{
		int v1,v2,w;
		
		scanf("%d %d %d",&v1,&v2,&w);
		
		v1--; v2--;
		
		edg.emplace_back(v1,v2,w);
	}
	
	sort(edg.begin(),edg.end());
	
	int ans = 0;
	
	for(int i = 0;i<m;i++)
	{
		if(merge(edg[i].v1,edg[i].v2)) ans += edg[i].w;
	}
	
	printf("%d",ans);
	
	return 0;
}