[백준] 14688 - Minimum Cost Flow (c++)

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

 

문제 요약

정점 N개와 간선 M개로 이루어진 가중치 그래프가 주어진다. 각 간선은 활성화 상태와 비활성화 상태 중 하나를 가지며, 한 간선의 가중치를 D만큼 감소시킬 수 있는 강화 작업을 한 번 수행할 수 있다.

동작은 두 가지를 포함한다:

1. 간선 활성화: 현재 비활성화된 간선을 활성화한다.
2. 간선 비활성화: 현재 활성화된 간선을 비활성화한다.

초기 상태에서 최소한의 동작 횟수로 MST를 구성해라.

 

풀이 (MlogM)

• MST

D를 이용해 동작 횟수를 한 번 줄일 수 있는지 보는 문제이다.

최대 코스트 간선이 여러개라고 생각해보자. 이 중 인덱스가 N보다 크거나 같은게 없다면 D로 인해 바뀌는게 없다. 만약 있다면 최대 간선 중 하나를 가중치가 D 이하이고 인덱스가 N미만인 다른 간선으로 대체 할 수 있는지 보면 된다.

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

struct Djs {
    vector<int> p;
    Djs(int size) {
        p.resize(size,0);
    }
    int find(int a) {
        if (!p[a])
            return a;
        return p[a] = find(p[a]);
    }
    void Union(int a, int b) {
        p[find(a)] = find(b);
    };
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,m,d;cin>>n>>m>>d;
    vector<array<int,4>> ed;
    for(int i=1,u,v,c;i<=m;i++) {
        cin>>u>>v>>c,ed.push_back({c,i,u,v});
    }
    
    sort(ed.begin(),ed.end());
    Djs djs = Djs(n+1);
    int cnt=0;
    array<int,4> mxed;
    for(auto [c,idx,u,v]:ed) {
        if(djs.find(u)!=djs.find(v)) {
            djs.Union(u,v);
            //cout<<c<<'\n';
            if(idx>=n) {
                cnt++;
            }
            mxed={c,idx,u,v};
        }
    }
    djs = Djs(n+1);
    if(mxed[1]>=n) {
        for(auto [c,idx,u,v]:ed) {
        if(djs.find(u)!=djs.find(v)) {
            if(c<mxed[0]||(idx<n&&mxed[0]==c))
                djs.Union(u,v);
            else if(idx<n&&c<=d) {
                cnt--;
                break;
            }
        }
    }
    }
    cout<<cnt<<'\n';
}