[BOJ] 23743번: 방탈출

https://www.acmicpc.net/problem/23743

23743번: 방탈출

---

풀이 

새로운 0번 정점을 정의해서, i번 정점과 t[i]의 시간을 가지는 간선을 이은 후, MST를 구하면 된다.

처음에, 모든 정점들이 연결되어 있지 않을 때 되게 귀찮다고 생각했었는데, 공식 풀이를 보고 새 정점 만든 뒤 기존 정점들과 잇는 방식을 이용해 해결할 수 있음을 알게 되었다. 이와 같은 테크닉을 최대 유량 문제 풀 때 본 것 같은데, 잘 기억해 두어야겠다.

---

코드

MST는 크루스칼 알고리즘을 이용해 구현했다. 오랜만에 MST 구현해서 다시 공부하면서 코드를 짯다. 크루스칼 알고리즘 외울 때에는, '간선에 대해서 그리디 + 분리집합'을 생각하며 외워야겠다.

ll n, m;
vector<pair<ll, pll>> edges;
ll mst;

ll p[200005];

int find(int x)
{
    if(p[x]<0) return x;
    return p[x]=find(p[x]);
}

void merge(int a, int b)
{
    a=find(a); b=find(b);
    if(a==b) return;
    p[a]=b;
}

void solve()
{
    cin>>n>>m;
    memset(p, -1, sizeof(p));
    for(ll i=0;i<m;i++)
    {
        ll a, b, c; cin>>a>>b>>c;
        edges.push_back({c, {a, b}});
    }
    for(ll i=1;i<=n;i++) 
    {
        ll t; cin>>t;
        edges.push_back({t, {0, i}});
    }

    sort(edges.begin(), edges.end());
    for(ll i=0;i<edges.size();i++)
    {
        ll a=edges[i].Y.X;
        ll b=edges[i].Y.Y;
        ll c=edges[i].X;
        if(find(a)==find(b)) continue;
        merge(a, b);
        mst+=c;
    }
    cout<<mst;
}