C++ の動作確認をしてみた（５３５）

C++の練習を兼ねて, AtCoder Beginner Contest 218 の問題E (Destruction) を解いてみた.

■感想.
1. 問題E は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. Union-Find木, 最小全域木(Kruskal’s Algorithm) の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 218 解説の各リンクをご覧下さい.

■C++版プログラム(問題E／AC版).

// 解き直し.
// https://atcoder.jp/contests/abc218/editorial/2580
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using vl = vector<LL>;
using T3 = tuple<LL, int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
LL c[202020];
int a[202020], b[202020];

// https://github.com/atcoder/live_library/blob/master/uf.cpp
// UnionFind
// coding: https://youtu.be/TdR816rqc3s?t=726
// comment: https://youtu.be/TdR816rqc3s?t=6822
// -> 一部改変.
struct UnionFind{
    vi d;
    UnionFind(int n = 0): d(n, -1) {}
    int find(int x){
        return (d[x] < 0) ? x : (d[x] = find(d[x]));
    }
    bool unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(d[x] > d[y]) swap(x, y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    int size(int x){
        return -d[find(x)];
    }
};

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    LL cTotal = 0;
    rep(i, M){
        scanf("%d %d %lld", &a[i], &b[i], &c[i]);
        a[i]--;
        b[i]--;
        cTotal += c[i]; // コスト合計.
    }
    
    // 2. sort.
    vector<T3> t;
    rep(i, M) t.emplace_back(c[i], a[i], b[i]);
    sort(all(t));
    
    // 3. 最小全域木(Kruskal's Algorithm)を計算.
    // 競プロ典型 90 問 (049 - Flip Digits 2)
    // https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp
    LL cSum = 0;
    UnionFind uf(N + 2);
    rep(i, t.size()){
        // 3-1. グラフ情報.
        int u = get<1>(t[i]);
        int v = get<2>(t[i]);
        LL cost = get<0>(t[i]);
        
        // 3-2. コストが負.
        // -> 必ず, 辺を追加.
        if(cost < 0){
            uf.unite(u, v);
            cSum += cost;
        }
        
        // 3-3. コストがゼロ以上.
        // -> 最小全域木に必要な場合に, 追加.
        if(cost >= 0){
            if(!uf.same(u, v)){
                uf.unite(u, v);
                cSum += cost;
            }
        }
    }
    
    // 4. 出力.
    printf("%lld\n", cTotal - cSum);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc218/editorial/2580

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vl = vector<LL>;

using T3 = tuple<LL, int, int>;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define all(x) x.begin(), x.end()

LL c[202020];

int a[202020], b[202020];

// https://github.com/atcoder/live_library/blob/master/uf.cpp

// UnionFind

// coding: https://youtu.be/TdR816rqc3s?t=726

// comment: https://youtu.be/TdR816rqc3s?t=6822

// -> 一部改変.

struct UnionFind{

vi d;

UnionFind(int n = 0): d(n, -1) {}

int find(int x){

return (d[x] < 0) ? x : (d[x] = find(d[x]));

}

bool unite(int x, int y){

x = find(x);

y = find(y);

if(x == y) return false;

if(d[x] > d[y]) swap(x, y);

d[x] += d[y];

d[y] = x;

return true;

}

bool same(int x, int y){

return find(x) == find(y);

}

int size(int x){

return -d[find(x)];

}

};

int main(){

// 1. 入力情報.

int N, M;

scanf("%d %d", &N, &M);

LL cTotal = 0;

rep(i, M){

scanf("%d %d %lld", &a[i], &b[i], &c[i]);

a[i]--;

b[i]--;

cTotal += c[i]; // コスト合計.

}

// 2. sort.

vector<T3> t;

rep(i, M) t.emplace_back(c[i], a[i], b[i]);

sort(all(t));

// 3. 最小全域木(Kruskal's Algorithm)を計算.

// 競プロ典型 90 問 (049 - Flip Digits 2)

// https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp

LL cSum = 0;

UnionFind uf(N + 2);

rep(i, t.size()){

// 3-1. グラフ情報.

int u = get<1>(t[i]);

int v = get<2>(t[i]);

LL cost = get<0>(t[i]);

// 3-2. コストが負.

// -> 必ず, 辺を追加.

if(cost < 0){

uf.unite(u, v);

cSum += cost;

}

// 3-3. コストがゼロ以上.

// -> 最小全域木に必要な場合に, 追加.

if(cost >= 0){

if(!uf.same(u, v)){

uf.unite(u, v);

cSum += cost;

}

// 4. 出力.

printf("%lld\n", cTotal - cSum);

return 0;

}

[入力例]
4 5
1 2 1
1 3 1
1 4 1
3 2 2
4 2 2

[出力例]
4
※AtCoderテストケースより

[入力例]
3 3
1 2 1
2 3 0
3 1 -1

[出力例]
1
※AtCoderテストケースより

[入力例]
2 3
1 2 -1
1 2 2
1 1 3

[出力例]
5
※AtCoderテストケースより

[入力例]
5 7
1 3 4
3 4 3
1 2 -1
2 5 3
2 5 6
2 4 2
5 4 -2

[出力例]
13

※実際, 辺 1, 4, 5 を 取り除いて, 合計 4 + 3 + 6 = 13 の 報酬となる.

[入力例]
10 16
1 3 -4
7 1 3
5 3 2
3 6 -1
5 6 3
5 2 7
5 7 6
7 9 7
4 9 -3
8 9 11
4 8 4
4 2 5
2 8 6
2 10 2
6 10 7
8 10 9

[出力例]
49

※実際, 辺 5, 7, 8, 10, 13, 15, 16 を 取り除いて, 合計 3 + 6 + 7 + 11 + 6 + 7 + 9 = 49 の 報酬となる.

[入力例]

4 5

1 2 1

1 3 1

1 4 1

3 2 2

4 2 2

[出力例]

※AtCoderテストケースより

[入力例]

3 3

1 2 1

2 3 0

3 1 -1

[出力例]

※AtCoderテストケースより

[入力例]

2 3

1 2 -1

1 2 2

1 1 3

[出力例]

※AtCoderテストケースより

[入力例]

5 7

1 3 4

3 4 3

1 2 -1

2 5 3

2 5 6

2 4 2

5 4 -2

[出力例]

※実際, 辺 1, 4, 5 を取り除いて, 合計 4 + 3 + 6 = 13 の報酬となる.

[入力例]

10 16

1 3 -4

7 1 3

5 3 2

3 6 -1

5 6 3

5 2 7

5 7 6

7 9 7

4 9 -3

8 9 11

4 8 4

4 2 5

2 8 6

2 10 2

6 10 7

8 10 9

[出力例]

※実際, 辺 5, 7, 8, 10, 13, 15, 16 を取り除いて, 合計 3 + 6 + 7 + 11 + 6 + 7 + 9 = 49 の報酬となる.

■参照サイト
AtCoder Beginner Contest 218
Union-Find木
 競プロ典型 90 問の問題049

C++の練習を兼ねて, AtCoder Beginner Contest 218 の 問題E (Destruction) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Beginner Contest 218 の問題E (Destruction) を解いてみた.

コメントを残すコメントをキャンセル