2JINISHAPPY 2JINISHAPPY

MST는 그리디 알고리즘을 이용해서 구할 수 있는 트리의 한 형태이다. 연결 그래프(하나의 Connected Component로 이루어진 그래프)에서 생성할 수 있는 부분 그래프이기도 하다. 그래프의 형태를 한 네트워크 회선이 존재할 때, 네트워크 구축 비용을 최소로 하는 경우의 수를 찾고 싶을 때 쓰이기도 한다. 그래프 G=(V,E)와 같고, 각 edge에 weight가 주어져 있을 때, 아래의 두 조건을 만족하는 G'( V(G), T )가 MST이다. 1️⃣ G'은 Connected하다. 2️⃣ G'은 포함할 수 있는 edge들의 cost 총 합을 최소로 한다. 해당 그래프에서는 연두색으로 칠해진 edge들을 선택했을 때 모든 vertex를 포함할 수 있으면서, cost의 합을 최소로 할 수 있기 때..

www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 컴퓨터를 연결하는 네트워크(가중치 무방향 그래프)가 주어졌을 때, 해당 네트워크의 MST를 구하는 문제이다 MST는 프림 알고리즘으로 구할 수 잇다 #include #include #include #include #define INF 987654321 using namespace std; priority_queue pq; vector edge; int v, e, cost[10005], pre[10005], ans; bool visit[10005]; void prim(int u) { visit[u] =..