hihoCoder_#1109_スタック最適化Primアルゴリズム

#1109:最小生成ツリー三・スタック最適化Primアルゴリズム
時間制限:
10000ms
単一点時限:
1000ms
メモリの制限:
256MB
説明
2週間前に戻り、Kruscalアルゴリズムを用いて問題を解決することに成功した後、Hoさんは疑問を抱いた.いったい、このようなアルゴリズムがPrimよりも疎図上で最適化されているのはどこなのか.ヒント:理由もなく最適化されていません.
入力
各テストポイント(入力ファイル)には、テストデータのセットが1つしかありません.
テストデータのセット:
1行目2つ目の整数N,Mは,小Hiが所有する都市数と小Hiがルートを選別した本数を表す.
次のM行は、各行が1つの経路を記述し、i行目が3つの整数N 1_であるi, N2_i, V_iは、この路線の2つの端点と、この路線に道路を建設する費用をそれぞれ表す.
100%のデータに対して、N<=10^5、M<=10^6を満たし、任意のiにおいて1<=N 1_を満たすi, N2_i<=N, N1_i≠N2_i, 1<=V_i<=10^3.
100%のデータに対して、任意の2つの都市が互いに到着できるようにする案がある.
しゅつりょく
各試験データのセットについて、1つの整数Ansを出力し、いずれの都市も建設された道路を通じて互いに少なくとも必要な建設費用に到達できるようにする.
サンプル入力

5 29
1 2 674
2 3 249
3 4 672
4 5 933
1 2 788
3 4 147
2 4 504
3 4 38
1 3 65
3 5 6
1 5 865
1 3 590
1 4 682
2 4 227
2 4 636
1 4 312
1 3 143
2 5 158
2 3 516
3 5 102
1 5 605
1 4 99
4 5 224
2 4 198
3 5 894
1 5 845
3 4 7
2 4 14
1 4 185

サンプル出力

92

解析:疎図では、取得したエッジを最小スタックで維持します.実際には、1番ノードに接続されたエッジの集合をルートスタックで維持し、その中で最小のエッジを見つけるたびに、このエッジが接続されている点を1番ノードに追加します.実際には、新しい追加ノードで接続されているいくつかのエッジでスタックを更新します.
タイトルリンク:http://hihocoder.com/problemset/problem/1109
コードリスト:

#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

const int maxn = 100000 + 5;
const int maxv = 1000000 + 5;

struct Edge{
    int to;
    int dis;
    Edge(int to,int dis){
        this -> to = to;
        this -> dis = dis;
    }
    friend bool operator<(Edge a,Edge b){
        return a.dis>b.dis;
    }
};

int N,M,a,b,c;
vector<Edge>graph[maxn];
priority_queue<Edge>q;
bool vis[maxn];

void init(){
    while(!q.empty()) q.pop();
    for(int i=0;i<maxn;i++) graph[i].clear();
    memset(vis,false,sizeof(vis));
}

void input(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<M;i++){
        scanf("%d%d%d",&a,&b,&c);
        graph[a].push_back(Edge(b,c));
        graph[b].push_back(Edge(a,c));
    }
}

int queue_prim(){
    for(int i=0;i<graph[1].size();i++){
        q.push(graph[1][i]);
    }
    vis[1]=true;
    int left=N-1;
    int sum=0;
    while(!q.empty()&&left){
        Edge e=q.top(); q.pop();
        if(vis[e.to]) continue;
        sum+=e.dis;
        left--;
        vis[e.to]=true;
        for(int i=0;i<graph[e.to].size();i++){
            Edge t=graph[e.to][i];
            if(!vis[t.to]) q.push(t);
        }
    }return sum;
}

void solve(){
    printf("%d
",queue_prim());
}

int main(){
    init();
    input();
    solve();
    return 0;
}

primアルゴリズム(本題に関係なく):

#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

const int maxn = 1000 + 5;
const int max_dis = 1e9 + 5;

int n;
int graph[maxn][maxn];
int dis[maxn];
bool vis[maxn];

void init(){
    fill(dis,dis+n,max_dis);
    memset(vis,false,sizeof(vis));
}

void input(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        scanf("%d",&graph[i][j]);
}

int prim(){
    init();
    dis[0]=0;
    int sum=0;
    while(true){
        int v=-1;
        for(int i=0;i<n;i++){
            if(!vis[i] &&(v==-1 || dis[i]<dis[v]))
                v=i;
        }
        if(v==-1) break;
        sum+=dis[v];
        vis[v]=true;
        for(int i=0;i<n;i++){
            dis[i]=min(dis[i],graph[v][i]);
        }
    }return sum;
}

void solve(){
    printf("%d
",prim());
}

int main(){
    input();
    solve();
    return 0;
}