最小生成ツリー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;
}