Test/AOJ/Prim.test.cpp

View this file on GitHub
Last update: 2021-06-18 21:14:35+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_A&lang=jp

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_A&lang=jp"

#include<bits/stdc++.h>
using namespace std;

#include"../../Other/Template.cpp"
#include"../../Graph/Prim.cpp"

int main() {
    cin >> N;
    for(int i = 0;i < N;i++) {
        for(int j = 0;j < N;j++) {
            cin >> cost[i][j];
            if(cost[i][j] == -1) cost[i][j] = INF;
        }
    }
    cout << prim() << endl;
}

#line 1 "Test/AOJ/Prim.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_A&lang=jp"

#include<bits/stdc++.h>
using namespace std;

#line 1 "Other/Template.cpp"
constexpr int Inf = 2000000030;
constexpr long long INF= 2000000000000000000;

template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
#line 1 "Graph/Prim.cpp"
long long cost[2010][2010]; // cost[u][v]は辺e=(u,v)のコスト
long long mincost[2010]; // 集合Xからのへ辺の最小コスト
bool used[2010]; //すでに頂点iがXに含まれているか
int N,M; //頂点の個数、辺の本数

long long prim() {
    for(int i = 0;i < N;i++) {
        mincost[i] = INF;
        used[i] = false;
    }
    mincost[0] = 0;
    long long res = 0;
    while(true) {
        int v = -1;
        //Xに属さない頂点のうちXからの辺のコストが最小になる頂点を探す
        for(int u = 0;u < N;u++) {
            if(!used[u] && (v == -1 || mincost[u] < mincost[v])) {
                v = u;
            }
        }
        if(v == -1) break;
        used[v] = true; //頂点vをXに追加
        res += mincost[v];
        for(int u = 0;u < N;u++) {
            chmin(mincost[u],cost[v][u]);
        }
    }
    return res;
}
#line 8 "Test/AOJ/Prim.test.cpp"

int main() {
    cin >> N;
    for(int i = 0;i < N;i++) {
        for(int j = 0;j < N;j++) {
            cin >> cost[i][j];
            if(cost[i][j] == -1) cost[i][j] = INF;
        }
    }
    cout << prim() << endl;
}