C++ の動作確認をしてみた（２９７）

C++の練習を兼ねて, 全国統一プログラミング王決定戦予選/NIKKEI ProgrammingContest 2019 の問題E (Weights on Vertices and Edges) を解いてみた.

■感想.
1. 方針が見えなかったので, 解説を参照して実装して, ようやく, AC版となった.
2. Union-Find木の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 個人的には, 本問の実装に色々苦労したものの, 非常に面白い問題に感じた.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイト全国統一プログラミング王決定戦予選/NIKKEI ProgrammingContest 2019 解説をご覧下さい.

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

// 一部ロジック修正して, 再提出.
// 解き直し.
// https://img.atcoder.jp/nikkei2019-qual/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<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 pb push_back
#define a first
#define b second
#define all(x) x.begin(), x.end()

struct edge{
    int n; // 次の頂点.
    LL w;  // 重み.
};

struct info{
    int u, v; // 頂点.
    LL w;     // 重み.
    bool operator < (const info &E) const { return w > E.w; }
};

LL X[101010];           // 各頂点の重み.
vector<edge> G[101010]; // グラフ.

// 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{
    vector<int> d;
    vector<LL> weights;
    UnionFind(int n = 0): d(n, -1), weights(n, 0) {}
    void setWeights(int x, LL w){
        weights[x] = w;
    }
    int find(int x){
        if(d[x] < 0) return x;
        return 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;
        weights[x] += weights[y];
        return true;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    int size(int x){
        return -d[find(x)];
    }
    LL sum(int x){
        return weights[find(x)];
    }
};

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) scanf("%lld", &X[i]);
    vector<info> v;
    rep(i, M){
        int a, b;
        LL w;
        scanf("%d %d %lld", &a, &b, &w);
        a--, b--;
        
        // 辺情報を保存.
        if(a > b) swap(a, b);
        info e;
        e.u = a;
        e.v = b;
        e.w = w;
        v.pb(e);
        
        // グラフ.
        edge e1, e2;
        e1.n = b, e2.n = a;
        e1.w = w, e2.w = w;
        G[a].pb(e1);
        G[b].pb(e2);
    }
    
    // 2. sort.
    sort(all(v)); // 降順sort.
    // puts("--- v start ---");
    // for(auto &e : v) printf("%d %d %lld\n", e.u, e.v, e.w);
    // puts("---- v end ----");
    
    // 3. 辺の重みが小さい順に, 辺を追加.
    UnionFind uf(N);
    rep(i, N) uf.setWeights(i, X[i]);
    set<P> res; // 残す辺(候補).
    repr(i, v.size() - 1, 0){
        info e = v[i];
        int u = e.u;
        int v = e.v;
        LL  w = e.w;
        if(u > v) swap(u, v);
        if(!uf.same(u, v)) uf.unite(u, v);
        int r = uf.find(u);
        if(uf.sum(r) >= w) res.insert({u, v});
    }
    // puts("--- res start ---");
    // for(auto &e : res) printf("%d %d\n", e.a, e.b);
    // puts("---- res end ----");
    
    // 4. 辺の重みが大きい順に, 残す辺をチェック.
    set<P> eRes; // 残す辺.
    set<P> memo; // 訪問済みフラグ.
    function<void(int, LL)> f = [&](int sv, LL sw) {
        
        // 1. 初期化.
        priority_queue<pair<LL, int>> pq;
        
        // 2. 始点設定.
        pq.push({sw, sv});
        
        // 3. キュー pq が 空になるまで, 探索.
        while(!pq.empty()){
            // 4. 探索を継続するために, 頂点を取得.
            LL cw = pq.top().a;
            int cv = pq.top().b;
            pq.pop();
            
            // 5. 各隣接する頂点について確認.
            for(auto &ne : G[cv]){
                LL nw = ne.w;
                int nv = ne.n;
                int a = min(cv, nv), b = max(cv, nv);
                
                // 6. 辺を保存, 訪問済みフラグ設定.
                // nw <= cw でなく nw <= sw に ロジック修正.
                // ex.
                // 辺(辺の重み)について,
                // e1(16) -> e2(1) -> e3(8) -> e4(20) の 場合に, e1, e2, e3 までを取得する必要がある.
                // 実際, 取得される辺について, 以下のように, 異なる結果となる.
                // nw <= cw の 場合: e1, e2
                // nw <= sw の 場合: e1, e2, e3
                if(!memo.count({a, b}) && nw <= sw) eRes.insert({a, b}), pq.push({nw, nv});
                memo.insert({a, b});
            }
        }
    };
    rep(i, v.size()){
        // 辺 e を 取得.
        info e = v[i];
        int u = e.u;
        int v = e.v;
        LL w = e.w;
        if(u > v) swap(u, v);
        
        // 今回の結果から, 残す辺に含まれるか？
        // -> 重みが, 辺 e 以下の辺も, 辿っていける場合は, すべて残す.
        if(res.count({u, v})) f(u, w);
    }
    // for(auto &p : eRes) printf("%d %d\n", p.a, p.b);
    
    // 5. 残す辺数を計算.
    int ans = M - eRes.size();
    
    // 6. 出力.
    printf("%d\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

// 一部ロジック修正して, 再提出.

// 解き直し.

// https://img.atcoder.jp/nikkei2019-qual/editorial.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<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 pb push_back

#define a first

#define b second

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

struct edge{

int n; // 次の頂点.

LL w; // 重み.

};

struct info{

int u, v; // 頂点.

LL w; // 重み.

bool operator < (const info &E) const { return w > E.w; }

};

LL X[101010]; // 各頂点の重み.

vector<edge> G[101010]; // グラフ.

// 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{

vector<int> d;

vector<LL> weights;

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

void setWeights(int x, LL w){

weights[x] = w;

}

int find(int x){

if(d[x] < 0) return x;

return 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;

weights[x] += weights[y];

return true;

}

bool same(int x, int y){

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

}

int size(int x){

return -d[find(x)];

}

LL sum(int x){

return weights[find(x)];

}

};

int main(){

// 1. 入力情報.

int N, M;

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

rep(i, N) scanf("%lld", &X[i]);

vector<info> v;

rep(i, M){

int a, b;

LL w;

scanf("%d %d %lld", &a, &b, &w);

a--, b--;

// 辺情報を保存.

if(a > b) swap(a, b);

info e;

e.u = a;

e.v = b;

e.w = w;

v.pb(e);

// グラフ.

edge e1, e2;

e1.n = b, e2.n = a;

e1.w = w, e2.w = w;

G[a].pb(e1);

G[b].pb(e2);

}

// 2. sort.

sort(all(v)); // 降順sort.

// puts("--- v start ---");

// for(auto &e : v) printf("%d %d %lld\n", e.u, e.v, e.w);

// puts("---- v end ----");

// 3. 辺の重みが小さい順に, 辺を追加.

UnionFind uf(N);

rep(i, N) uf.setWeights(i, X[i]);

set<P> res; // 残す辺(候補).

repr(i, v.size() - 1, 0){

info e = v[i];

int u = e.u;

int v = e.v;

LL w = e.w;

if(u > v) swap(u, v);

if(!uf.same(u, v)) uf.unite(u, v);

int r = uf.find(u);

if(uf.sum(r) >= w) res.insert({u, v});

}

// puts("--- res start ---");

// for(auto &e : res) printf("%d %d\n", e.a, e.b);

// puts("---- res end ----");

// 4. 辺の重みが大きい順に, 残す辺をチェック.

set<P> eRes; // 残す辺.

set<P> memo; // 訪問済みフラグ.

function<void(int, LL)> f = [&](int sv, LL sw) {

// 1. 初期化.

priority_queue<pair<LL, int>> pq;

// 2. 始点設定.

pq.push({sw, sv});

// 3. キュー pq が空になるまで, 探索.

while(!pq.empty()){

// 4. 探索を継続するために, 頂点を取得.

LL cw = pq.top().a;

int cv = pq.top().b;

pq.pop();

// 5. 各隣接する頂点について確認.

for(auto &ne : G[cv]){

LL nw = ne.w;

int nv = ne.n;

int a = min(cv, nv), b = max(cv, nv);

// 6. 辺を保存, 訪問済みフラグ設定.

// nw <= cw でなく nw <= sw にロジック修正.

// ex.

// 辺(辺の重み)について,

// e1(16) -> e2(1) -> e3(8) -> e4(20) の場合に, e1, e2, e3 までを取得する必要がある.

// 実際, 取得される辺について, 以下のように, 異なる結果となる.

// nw <= cw の場合: e1, e2

// nw <= sw の場合: e1, e2, e3

if(!memo.count({a, b}) && nw <= sw) eRes.insert({a, b}), pq.push({nw, nv});

memo.insert({a, b});

}

};

rep(i, v.size()){

// 辺 e を取得.

info e = v[i];

int u = e.u;

int v = e.v;

LL w = e.w;

if(u > v) swap(u, v);

// 今回の結果から, 残す辺に含まれるか？

// -> 重みが, 辺 e 以下の辺も, 辿っていける場合は, すべて残す.

if(res.count({u, v})) f(u, w);

}

// for(auto &p : eRes) printf("%d %d\n", p.a, p.b);

// 5. 残す辺数を計算.

int ans = M - eRes.size();

// 6. 出力.

printf("%d\n", ans);

return 0;

}

[入力例]
4 4
2 3 5 7
1 2 7
1 3 9
2 3 12
3 4 18

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

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

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

[入力例]
10 9
81 16 73 7 2 61 86 38 90 28
6 8 725
3 10 12
1 4 558
4 9 615
5 6 942
8 9 918
2 7 720
4 7 292
7 10 414

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

[入力例]
7 11
5 1 1 3 1 2 2
1 7 11
7 2 19
1 2 8
5 2 23
1 5 17
2 3 10
2 4 7
4 5 16
4 6 13
6 3 2
1 4 18

[出力例]
5

[入力例]
10 8
1 1 2 5 7 2 3 1 1 1
6 7 4
7 8 7
1 3 10
1 2 19
2 10 2
3 9 17
9 4 3
3 5 8

[出力例]
3

[入力例]

4 4

2 3 5 7

1 2 7

1 3 9

2 3 12

3 4 18

[出力例]

※AtCoderテストケースより

[入力例]

6 10

4 4 1 1 1 7

3 5 19

2 5 20

4 5 8

1 6 16

2 3 9

3 6 16

3 4 1

2 6 20

2 4 19

1 2 9

[出力例]

※AtCoderテストケースより

[入力例]

10 9

81 16 73 7 2 61 86 38 90 28

6 8 725

3 10 12

1 4 558

4 9 615

5 6 942

8 9 918

2 7 720

4 7 292

7 10 414

[出力例]

※AtCoderテストケースより

[入力例]

7 11

5 1 1 3 1 2 2

1 7 11

7 2 19

1 2 8

5 2 23

1 5 17

2 3 10

2 4 7

4 5 16

4 6 13

6 3 2

1 4 18

[出力例]

[入力例]

10 8

1 1 2 5 7 2 3 1 1 1

6 7 4

7 8 7

1 3 10

1 2 19

2 10 2

3 9 17

9 4 3

3 5 8

[出力例]

■参照サイト
全国統一プログラミング王決定戦予選/NIKKEI ProgrammingContest 2019
Union-Find木

C++の練習を兼ねて, 全国統一プログラミング王決定戦予選/NIKKEI ProgrammingContest 2019 の 問題E (Weights on Vertices and Edges) を解いてみた.

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

C++の練習を兼ねて, 全国統一プログラミング王決定戦予選/NIKKEI ProgrammingContest 2019 の問題E (Weights on Vertices and Edges) を解いてみた.

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