【ACM】- HDU.1863円滑工事【最小生成木】

【目次】

タイトルリンク

テーマ分析

解題構想

|Kruskalアルゴリズム+並列調査セット(スタック最適化priority_queue)

|Kruskalアルゴリズム+並列調査セット(sort()

|Primeアルゴリズム-(隣接テーブルバージョン)

|Primeアルゴリズム-(隣接テーブルバージョン)(スタック最適化-priority_queue)

|Primeアルゴリズム-(隣接マトリクスバージョン)

タイトルリンク
テーマ分析
最小生成ツリー問題、パスと
問題を解く構想.
最小生成ツリーの母題として、それぞれ以下のいくつかの方法で実現される:1、Kruskalアルゴリズム+並列調査セット;2、Primeアルゴリズム(隣接マトリクスバージョン)3、Primeアルゴリズム(隣接テーブルバージョン)それぞれスタック構造(priority_queue)で最適化
|Kruskalアルゴリズム+並列調査セット(スタック最適化priority_queue)

#include
#include
#include
#include

using namespace std;
const int maxn = 110;

struct edge{
    int u, v, cost;
    edge() {}
    edge(int _u, int _v, int _cost) : u(_u), v(_v), cost(_cost) {} //    ，      
    bool operator < (const edge& n) const { //     
        return cost > n.cost; //   sort      
    }
};
int N, M;
int far[maxn]; //   

//  
int find_root(int a) {
    int root = a;
    while(root != far[root]) root = far[root];

    while(a != far[a]) { //    
        int cur = a;
        a = far[a];
        far[cur] = root;
    }
    return root;
}

//    
void union_set(int a, int b) {
    int root_a = find_root(a);
    int root_b = find_root(b);
    if(a != b){
        far[root_b] = root_a;
    }
}

int kruskal(priority_queue E) {
    for(int i = 1; i <= N; i++) far[i] = i; //      
    int ans = 0;//   
    int edge_num = 0; //      
    int cnt = N; //    

    for(int i = 0; i < M; i++) {
        edge e = E.top(); E.pop(); //get fisrt edge
        int root_u = find_root(e.u);
        int root_v = find_root(e.v);

        if(root_u != root_v) {
            union_set(root_u, root_v);
            edge_num++;
            cnt--; //    -1
            ans += e.cost;
        }
        if(edge_num == N - 1) break;  //       -1
    }
    if(cnt != 1) return -1;//       （edge_num == N - 1     ）
    else return ans;

}//kruskal

int main() {
    int a, b, cost;
    while(scanf("%d %d", &M, &N) != EOF) {
        if(M == 0) break;
        priority_queue E; //     ( clear()  ，          )
                                //    sort()      
        for(int i = 0; i < M; i++) {
            scanf("%d %d %d", &a, &b, &cost);
            E.push(edge(a, b, cost)); //   
        }

        int ans = kruskal(E);
        if(ans == -1) printf("?
");
        else printf("%d
", ans);

    }//while

    system("pause");
    return 0;
}

|Kruskalアルゴリズム+並列調査セット(sort()

#include
#include
#include
#include

using namespace std;
const int maxn = 110;

int N, M;
int far[maxn]; //   
struct edge{
    int u, v, cost;
    bool operator < (const edge& n) const { //     
        return cost < n.cost;
    }
}E[maxn];

bool cmp(edge e, edge f) { //           
    return e.cost < f.cost;
}

//  
int find_root(int a) {
    int root = a;
    while(root != far[root]) root = far[root];

    while(a != far[a]) { //    
        int cur = a;
        a = far[a];
        far[cur] = root;
    }
    return root;
}

//    
void union_set(int a, int b) {
    int root_a = find_root(a);
    int root_b = find_root(b);
    if(a != b){
        far[root_b] = root_a;
    }
}

int kruskal() {
    for(int i = 1; i <= N; i++) far[i] = i; //      
    sort(E, E + M); //     （        priority_queue）
    //sort(E, E + M, cmp);
    int ans = 0;//   
    int edge_num = 0; //      
    int cnt = N; //    
    for(int i = 0; i < M; i++) {

        int root_u = find_root(E[i].u);
        int root_v = find_root(E[i].v);
        if(root_u != root_v) {
            union_set(root_u, root_v);
            edge_num++;
            cnt--; //    -1
            ans += E[i].cost;
        }
        if(edge_num == N - 1) break;  //       -1
    }
    if(cnt != 1) return -1;//       
    else return ans;

}//kruskal

int main() {
    int a, b, cost;
    while(scanf("%d %d", &M, &N) != EOF) {
        if(M == 0) break;

        for(int i = 0; i < M; i++) {
            scanf("%d %d %d", &a, &b, &cost);
            E[i].u = a; E[i].v = b;
            E[i].cost = cost;
        }

        int ans = kruskal();
        if(ans == -1) printf("?
");
        else printf("%d
", ans);

    }//while

    system("pause");
    return 0;
}

|Primeアルゴリズム-(隣接テーブルバージョン)

#include
#include
#include
#include
#include

using namespace std;
const int maxn = 110;
const int INF = 0x3fffffff;

int d[maxn];
int vis[maxn];
struct edge {
    int v, cost; //end, cost
    edge() {}
    edge(int _v, int _cost) : v(_v), cost(_cost) {} //    ，      
};

vector Adj[maxn]; //Adjacency list
int N, M;

int prime(int st) {
    fill(d, d + maxn, INF);
    memset(vis, false, sizeof(vis));
    d[st] = 0;//start
    int ans = 0;

    for(int i = 1; i <= N; i++) { // add all N nodes
        int u = - 1, min_cost = INF;
        for(int j = 1; j <= N; j++) {
            if(vis[j] == false && d[j] < min_cost) {
                min_cost = d[j];
                u = j;
            }
        }
        if(u == -1) return -1;
        vis[u] = true; //add this node
        ans += d[u]; //    

        for(int j = 0; j < Adj[u].size(); j++) {
            int v = Adj[u][j].v, cost = Adj[u][j].cost;
            if(vis[v] == false && cost < d[v])
                d[v] = cost;
        }
    }//for - i;
    return ans;
}

int main() {
    int st, ed, cost;
    edge e;
    while(scanf("%d %d", &M, &N) != EOF) {
        if(M == 0) break;
        for(int i = 1; i <= N; i++) Adj[i].clear();
        for(int i = 0; i < M; i++) {//input info of edges
            scanf("%d %d %d", &st, &ed, &cost);
            Adj[st].push_back(edge(ed, cost)); //underected graph
            Adj[ed].push_back(edge(st, cost));
        }

        int ans = prime(1);//start from node 1
        if(ans == -1) printf("?
");
        else printf("%d
", ans);
    }

    system("pause");
    return 0;
}

|Primeアルゴリズム-(隣接テーブルバージョン)(スタック最適化-priority_queue)
考え方:空間で時間を変える

はpriority_queueで保存され、最短距離の選択を最適化する.

元の配列d[]はまだ保持する必要があります.そうしないと、距離更新はキューで操作できません.

新しい距離は直接キューに入れればいいです.同じ点までの距離は複数発生しますが、最後に最小のものを追加するに違いありません.

以降はvis[]のマークにより、マークされたノードまでのエッジが選択される.

時間複雑度:従来のアルゴリズムの時間度はO(V^2)であり、スタック最適化後も外層サイクルはO(V)であるが、内層検索の最短距離はO(logV)であり、プロセス全体のエッジは1回アクセスされ、O(E)であり、時間複雑度はO(VlogV + E)に低下した.

#include
#include
#include
#include
#include
#include

using namespace std;
const int maxn = 110;
const int INF = 0x3fffffff;

//    -   【    -       】
struct dis{
    int u, d;
    dis() {}
    dis(int _u, int _d) : u(_u), d(_d) {}
    bool operator < (const dis & D) const {
        return d > D.d; //      
    }
};

priority_queue D; //          ；  
int d[maxn];  //              ，    
bool vis[maxn];
struct edge {
    int v, cost; //end, cost
    edge() {}
    edge(int _v, int _cost) : v(_v), cost(_cost) {} //    ，      
};

vector Adj[maxn]; //Adjacency list
int N, M;

int prime(int st) {
    for(int i = 1; i <= N; i++) { //     
        if(i == st) D.push(dis(i, 0)); //  
        else D.push(dis(i, INF));
    }
    fill(d, d + maxn, INF);
    memset(vis, false, sizeof(vis));
    d[st] = 0;
    int ans = 0;

    for(int i = 1; i <= N; i++) { //add all N nodes
        while(vis[D.top().u] == true) D.pop(); //    
        if(D.top().d == INF) return -1; //     ，        
        int u = D.top().u, min_cost = D.top().d; //      
        D.pop();

        vis[u] = true; //add this node
        ans += min_cost; //    

        for(int j = 0; j < Adj[u].size(); j++) { 
            int v = Adj[u][j].v, cost = Adj[u][j].cost;
            if(vis[v] == false && cost < d[v]) {
                d[v] = cost; 
                D.push(dis(v, cost)); //    （              ，         ）
            }
        }
    }//for - i;
    return ans;
}

//       
int main() {
    int st, ed, cost;
    edge e;
    while(scanf("%d %d", &M, &N) != EOF) {
        if(M == 0) break;
        for(int i = 1; i <= N; i++) Adj[i].clear();
        for(int i = 0; i < M; i++) {//input info of edges
            scanf("%d %d %d", &st, &ed, &cost);
            Adj[st].push_back(edge(ed, cost)); //underected graph
            Adj[ed].push_back(edge(st, cost));
        }

        int ans = prime(1);//start from node 1
        if(ans == -1) printf("?
");
        else printf("%d
", ans);
    }

    system("pause");
    return 0;
}

|Primeアルゴリズム-(隣接マトリクスバージョン)
【隣接マトリクスバージョンスタックの最適化の価値は大きくない.最小距離の選択を最適化しても、距離が更新されるたびにすべてのエッジを遍歴するため、primeアルゴリズムは稠密図に多く使用される.】

#include
#include
#include
#include

using namespace std;
const int INF = 0x3fffffff;
const int maxn = 110;

int N, M;
int G[maxn][maxn]; 
int d[maxn]; //Prime
bool vis[maxn];

//Prime  
int prime(int st) {
    fill(d, d + maxn, INF);
    fill(vis, vis + maxn, false);

    int ans = 0;
    d[st] = 0; //  （ ）
    for(int i = 1; i <= N; i++) { //      

        int u = -1, min_cost = INF;
        for(int j = 1; j <= N; j++) {
            if(vis[j] == false && d[j] < min_cost) {//         
                min_cost = d[j];
                u = j;
            }
        }
        if(u == -1) return -1;//    ，  MST     WA 
        vis[u] = true; //    
        ans += d[u]; //    

        for(int v = 1; v <= N; v++) { //      
            if(vis[v] == false && G[u][v] < d[v]){
                d[v] = G[u][v];
            }
        }//for - v

    }//for - i
    return ans;
}//prime()

int main() {
    int a, b, cost;
    while(scanf("%d %d", &M, &N) != EOF) {
        if(M == 0) break;

        fill(G[0], G[0] + maxn * maxn, INF);

        for(int i = 0; i < M; i++) {
            scanf("%d %d %d", &a, &b, &cost);
            G[a][b] = cost;
            G[b][a] = cost;
        }

        int ans = prime(1); // 1       
        if(ans == -1) printf("?
");
        else printf("%d
", ans);

    }//while

    system("pause");
    return 0;
}