[백준] 6611 - Simon the Spider (c++)

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

 

문제 요약

정점이 N개 간선이 M개인 그래프가 주어진다. 그래프의 간선들로 스패닝 트리를 만들어야 한다.

쓴 간선들 중 가장 비싼 간선의 가중치는 -가 될 때, 스패닝 트리를 만드는 최소 비용을 구해라.

 

풀이 (N^3)

• MST
• DP

일단 MST를 하나 구성한다. 간선 i에 대해 i가 가장 큰 간선이라 가정하고 MST에 삽입시킨다. 이 때 생기는 사이클에 가장 큰 간선을 하나 지운다. 이걸 모든 i에 대해 취해주며 min값을 구해주면 된다.

DFS로 사이클에서 가장 큰 간선을 찾아주는 O(NM) 풀이를 할 수도 있고, DP로 전처리 해줘도 된다.

난 DP로 전처리 하는 방법을 사용했다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    cin.tie(0)->sync_with_stdio(0); 
    int n,m;
    while(cin>>n>>m) {
        vector<array<int,3>> ed(m);
        for(auto&[c,x,y]:ed)
            cin>>x>>y>>c;
        sort(ed.begin(),ed.end());
        vector<bool> in(m);
        vector<vector<int>> con(n+1,vector<int>(n+1));
        ll mst=0,s=0;
        for(auto&[c,u,v]:ed) {
            if(!con[u][v]) {
                s++;
                mst+=c;
                con[u][v]=con[v][u]=c;
                vector<int> l{u},r{v};
                for(int i=1;i<=n;i++) {
                    if(con[i][u])
                        l.push_back(i);
                    if(con[i][v])
                        r.push_back(i);
                }
                for(int&x:l) {
                    for(int&y:r) {
                        if(con[x][y])continue;
                        con[x][y]=con[y][x]=max(con[x][y],c);
                    }
                }
            }
        }
        if(s<n-1) {
            cout<<"disconnected"<<'\n';
            continue;
        }
        ll mn=1e18;
        for(auto&[c,u,v]:ed) 
            mn=min(mn,mst-con[u][v]-c);
        cout<<mn<<'\n';
    }
}