頭良くなりたい人

文系大学生shadeのブログです。競技プログラミングや人文学の話題,受験ネタなど。

AOJ ALDS1で典型手法を練習する―グラフ編―

話には聞くグラフ理論なるものについて,そろそろ体系的に練習したいと思ったので,Aizu Online Judgeのコース問題を解いてみました。

11_A~C はプログラム上でグラフを扱う練習のような問題だったので,よりアルゴリズムっぽい 11_D~12_C を掲載しています。

問題はこちら onlinejudge.u-aizu.ac.jp

11_D: 連結成分分解

コメント

連結成分分解というタイトルですが,連結成分ごとの頂点集合を作ったりするのではなく,Union-Find木というデータ構造を用います。

2 頂点 i,j が同一連結成分に含まれる \Leftrightarrow i,j が同一のUnion-Find木に属する」です。

Union-Find木については,以下の記事を参考にしました(ソースコードも使わせていただきました)。 qiita.com

コード

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define ALL(n) begin(n),end(n)
#define VMAX 50
#define EMAX 500
#define DMAX 20
#define TRUE 1
#define FALSE 0
#define NOTUSED 0
#define END -1
#define ROOT -1
using Graph=vector<vector<int>>;

struct UnionFind {
    vector<int> par; 

    UnionFind(int N) : par(N) {
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) {
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y); 
        if (rx == ry) return; 
        par[rx] = ry; 
    }

    bool same(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main(){
    // 友達関係の受け取り
    int n,m;
    cin>>n>>m;

    UnionFind G(n);

    REP(i,m){
        int a,b;
        cin>>a>>b;

        G.unite(a,b);
    }
    
    // 質問の受け取り
    int q;
    cin>>q;

    vector<pair<int,int>> link(q);
    REP(i,q){
        cin>>link[i].first>>link[i].second;
    }

    // 判定
    REP(i,q){
        if(G.same(link[i].first,link[i].second)){
            cout<<"yes"<<endl;
        }else{
            cout<<"no"<<endl;
        }
    }
}

12_A: 最小全域木

コメント

全域木とは,あるグラフ G=(V,E) に対して,T=(V,E')E'E の部分集合)であるような木 T のことです。最小全域木は,そのような全域木の中で,各辺の重みの和が最小であるものをいいます。

最小全域木を求めるアルゴリズムとしては,プリムのアルゴリズムクラスカルアルゴリズムが有名(らしい)です。今回はそのうちプリムのアルゴリズムを実装しています。

プリムのアルゴリズムは,頂点が一つだけの状態から,できるだけ重みが小さい辺(とその頂点)を選んでいく貪欲法の一種ですが,詳しくはプリム法 - Wikipediaを参照してください。

コード

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
using Graph=vector<vector<int>>;

int n;
vector<int> included;

int Prim(const Graph &G,int v,int &cost){
    // 頂点vは木に含まれた
    included.push_back(v);
    // n頂点全てが木に含まれていれば終了
    if(included.size()==n) return cost;

    int min_=2001;
    int to=-1;
    // 木に接続した頂点(とその辺)のうち,最も重みの小さいものを採用
    for(int x:included){
        for(int y=0; y<n; y++){
            if(G[x][y]<min_ && G[x][y]!=-1){
                // yがincludedに含まれている場合,何もしない
                if(find(included.begin(),included.end(),y)!=included.end()){
                    continue;
                }
                min_=G[x][y];
                to=y;
            }
        }
    }

    // 頂点toを追加して,Primを呼び出す
    cost+=min_;
    return Prim(G,to,cost);
}

int main(){
    cin>>n;
    
    // 隣接行列を受け取る
    Graph G(n,vector<int>(n));
    REP(i,n){
        REP(j,n){
            cin>>G[i][j];
        }
    }

    int cost=0;

    cout<<Prim(G,0,cost)<<endl;
}

12_B: 単一始点最短経路

コメント

グラフは隣接行列として受け取り,ダイクストラを用います。

ダイクストラ法 - Wikipediaに載っている疑似コードがわかりやすかったので,そのままコード化しています({\rm prev}(v) は必要がないので調べていません)。

グラフが連結であることは前提にしています(当たり前?)。

コード

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define ALL(n) begin(n),end(n)
const int INF=1000000000;

using Graph=vector<vector<int>>;

int n;
vector<int> d;

void Dijkstra(const Graph &G){
    // 暫定の最短距離,頂点番号
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> que;
    que.emplace(d[0],0);

    // 距離を確定すべき頂点がなくなるまで続ける
    while(!que.empty()){
        pair<int,int> p=que.top();
        que.pop();
        int v=p.second;
        
        // 最短距離より大きい場合は無視
        if(d[v]<p.first) continue;

        REP(i,n){
            // 辺(v,i)がなければ無視
            if(G[v][i]==INF) continue;

            // 辺(v,i)を採用して距離が短くなるならば,暫定的に採用
            if(d[i]>d[v]+G[v][i]){
                d[i]=d[v]+G[v][i];
                que.emplace(d[i],i);
            }
        }
    }
}

int main(){
    cin>>n;

    // グラフの受け取り
    Graph G(n,vector<int>(n));
    REP(i,n){
        int u,k;
        cin>>u>>k;
        G[u].assign(n,INF);
        REP(j,k){
            int v,c;
            cin>>v>>c;
            G[u][v]=c;
        }
    }

    // d[i]=(無限大) で初期化
    d.assign(n,INF);
    d[0]=0;

    Dijkstra(G);

    REP(i,n){
        cout<<i<<" "<<d[i]<<endl;
    }
}

12_C: 単一始点最短経路 II

コメント

これ,12_Bと同じ問題(計算量が多い)なんですが,MLE(メモリ超過)で落とされました。メモリ制限131072 KBって結構厳しいですね。

隣接行列は存在しない辺の分もメモリを消費するのでメモリ効率が悪いらしいです。隣接リストなど別の方法でグラフを表せば通ると思うのですが,今回は一旦保留にしておきます。解いたら追記しておこうと思います。

にほんブログ村 IT技術ブログへ
にほんブログ村