백준21086 Smol Vertex Cover

작성일 | In

문제 링크

  • http://icpc.me/21086

사용 알고리즘

  • Edmond’s blossom algorithm
  • 2-SAT

시간복잡도

  • $O(N^3)$

풀이

최대 매칭의 크기를 $M$, 최소 정점 덮개의 크기를 $C$라고 합시다. $M \leq C$인 것은 자명하기 때문에 $C = M$인 경우와 $C = M+1$인 경우로 나눠서 생각하면 됩니다. 일단 Edmond’s blossom algorithm을 이용해 $O(N^3)$ 시간에 최대 매칭을 구합시다.

만약 $C=M$이라면 각 매칭의 끝점 중 정확히 한 정점이 정점 덮개에 포함되어야 합니다. 또한 정점 덮개의 조건을 만족하기 위해서 각 간선의 끝점 중 하나 이상이 정점 덮개에 포함되어야 합니다. 두 조건 모두 2-SAT으로 모델링할 수 있으므로 $O(N^2)$ 시간에 판별할 수 있습니다.

이제 $C=M+1$인 경우를 생각해 봅시다. 매칭마다 정점을 하나씩 선택한 다음 추가로 하나를 더 선택해야 합니다. 구체적으로, 매칭에 포함되지 않은 정점을 선택하거나, 한 매칭의 양쪽 끝점을 모두 선택해야 합니다.
매칭에 포함되지 않은 정점을 선택하는 것은 $N-2M$가지의 경우를 확인하면 되고, 한 매칭의 양쪽 끝점을 모두 선택하는 것은 $M$가지 경우를 확인하면 됩니다. 두 케이스 모두 2-SAT으로 모델링할 수 있으므로 $O(N^3)$ 시간에 판별할 수 있습니다.

따라서 전체 문제를 $O(N^3)$ 시간에 해결할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
vector<int> Check(int n, const vector<pair<int,int>> &edge, const vector<pair<int,int>> &match,
                  int use_vertex, int use_match){
    // vertex cover condition
    two_sat::clear();
    for(const auto &[a,b] : edge) two_sat::addEdge(a+n, b), two_sat::addEdge(b+n, a);

    // matching vertex
    vector<int> use(n+1);
    for(int i=0; i<match.size(); i++){
        const auto &[a,b] = match[i];
        if(i == use_match) two_sat::addEdge(a+n, a), two_sat::addEdge(b+n, b);
        else two_sat::addEdge(a, b+n), two_sat::addEdge(b, a+n);
        use[a] = use[b] = 1;
    }

    // not matching vertex
    for(int i=1; i<=n; i++) if(!use[i] && i != use_vertex) two_sat::addEdge(i, i+n);
    if(use_vertex != -1) two_sat::addEdge(use_vertex+n, use_vertex);

    return two_sat::run(n);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N, M; cin >> N >> M;
    if(M == 0){ cout << 0; return 0; }
    vector<pair<int,int>> E(M);
    for(auto &[a,b] : E) cin >> a >> b, blossom::addEdge(a, b);
    vector<pair<int,int>> Match = blossom::run(N);

    if(auto Cover = Check(N, E, Match, -1, -1); !Cover.empty()){
        cout << Cover.size() << "\n";
        for(auto c : Cover) cout << c << " ";
        return 0;
    }

    vector<int> U(N + 1);
    for(auto [a,b] : Match) U[a] = U[b] = 1;

    for(int i=1; i<=N; i++){
        if(U[i]) continue;
        if(auto Cover = Check(N, E, Match, i, -1); !Cover.empty()){
            cout << Cover.size() << "\n";
            for(auto c : Cover) cout << c << " ";
            return 0;
        }
    }

    for(int i=0; i<Match.size(); i++){
        if(auto Cover = Check(N, E, Match, -1, i); !Cover.empty()){
            cout << Cover.size() << "\n";
            for(auto c : Cover) cout << c << " ";
            return 0;
        }
    }

    cout << "not smol";
}