最小生成ツリーprimeアルゴリズムとクルーズカールアルゴリズム


primeアルゴリズム
欲張りな考えを用いて,現在の点から最も近い距離の辺は必ず最小生成木にある.
#include
using namespace std;
#define maxn 5005
#define inf 1e9
typedef long long ll;
int n,m,mat[maxn][maxn],vis[maxn]; //mat  ,vis           
bool flag[maxn]; //                 
ll slove()
{
    int ans = 0;
    flag[1] = 1;
    for(int i = 1; i <= n; i++)  //   1    
    {
        vis[i] = mat[1][i];
    }

    for(int i = 1; i < n; i++)    
    {

        int mi = inf,next;
        for(int j = 1; j <= n; j++)  //                
        {
            if(flag[j]==0 && vis[j]> n >> m;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            mat[i][j] = inf;

    for(int i = 1; i <= m; i++)
    {
        int x,y,z;
        cin >> x >> y >> z;
        if(mat[x][y] > z)
            mat[x][y] = mat[y][x] = z; //     
    }
    cout << slove() << endl;
    return 0;
}

クルーズカールアルゴリズム
エッジに重点を置き、小さなソートでエッジを選択し、ループが発生しないことを確認します.
#include
#pragma GCC optimize(2)
using namespace std;
#define maxn 200005
#define mod 1e9+7
#define inf 1e18
typedef long long ll;
struct Why
{
    ll a,b,c;
}arr[maxn];
ll n,m,r[maxn],ans,num;
bool cmp(Why a,Why b)
{
    return a.c < b.c;
}
ll fi(ll x)
{
    return r[x] == x? x: r[x] = fi( r[x] );
}
ll slove()
{
        for(ll i = 1; i <= m; i++)
        {
            if( fi(arr[i].a) != fi(arr[i].b)  )
            {
                 r[ fi( arr[i].b  ) ] =  arr[i].a ;
                 ans += arr[i].c;
                 num++;
            }
            if(num == n-1)
                break;
        }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);

    cin >> n >> m;

    for(ll i = 1; i <= m; i++)
        cin >> arr[i].a >> arr[i].b >> arr[i].c;

    sort(arr+1,arr+1+m,cmp);

    for(ll i = 1; i <= n; i++)
        r[i] = i;

    cout << slove() << endl;

    return 0;
}