글 읽기 - 크루스칼 알고리즘이 어디서 잘 안되는지 모르겠습니다..

skyde47 5년 전 0

최소힙까지는 프림으로 풀어서 잘 되는거 같은데 크루스칼로 옮기니까 안되네요 어디가 문제일까요 ㅠㅠ

#include
using namespace std;
#define INF 10001
#define Max 100000

int n, m, a, b, c,cnt=1;
int map[1001][1001];
int check[1001];
int rnk[1001];

struct line {
int x=0, y=0,data=INF;
};

line heap[Max];

line newline(int x,int y,int data)
{
    line l;
    l.x = x;
    l.y = y;
    l.data = data;
    return l;
}

int swap(int f, int s)
{
    line tmp = heap[f];
    heap[f] = heap[s];
    heap[s] = tmp;
    return s;
}

void push(line inp)
{
    if (cnt==1)heap[cnt++] = inp;
    else
    {
        heap[cnt] = inp;
        for (int i = cnt++; i > 1; i /= 2)
        {
            if (heap[i].data < heap[i / 2].data) swap(i, i/2);
            else break;
        }
    }
}

line pop()
    {
        line ret = heap[1];
        cnt--;
        heap[1] = heap[cnt];
        heap[cnt].data = INF;
        for (int i = 1; i < cnt;)
        {
            if (i * 2 > Max)break;
            if (heap[i].data < heap[i * 2].data&&heap[i].data < heap[i * 2 + 1].data) break;
            i = heap[i * 2].data > heap[i * 2 + 1].data? swap(i, i * 2 + 1):swap(i, i * 2);
        }
    return ret;
}

int Find_Set(int spot)
{
    while (spot != check[spot])spot = check[spot];
    return spot;
}

void Union(int spotA, int spotB)
{
    spotA = Find_Set(spotA);
    spotB = Find_Set(spotB);
    rnk[spotA] < rnk[spotB]?check[spotA] = check[spotB]:check[spotB]=check[spotA];
    if (rnk[spotA] == rnk[spotB])rnk[spotA]++;
}

int kruskal()
{
    int ret = 0;
    for (;cnt;)
    {
        line cur = pop();
        if (Find_Set(cur.x)==Find_Set(cur.y))continue;
        ret += cur.data;
        Union(cur.x, cur.y);
    }
    return ret;
}

int main()
{
    cin >> n >> m;
    for (int inp = 0; inp < m; inp++)
    {
        cin >> a >> b >> c;
        push(newline(a, b, c));
    }
    for (int i = 1; i <= n; i++)check[i] = i;
    cout << kruskal();
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

크루스칼 알고리즘이 어디서 잘 안되는지 모르겠습니다..

skyde47 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말