글 읽기 - 살려주세요 SMST를 못이기고 있습니다

jin8431 1년 전 1

게시판에 있는 모든 테스트 케이스는 잘 돌아가는데 정작 돌리면 55%에서 틀렸다고 나옵니다 ㅜㅜ

p_cost[x][2]의 의미는 x의 2^2번째 부모까지 간선들 중 가장 큰 값이고

s_cost는 마찬가지로 부모까지의 간선들 중 두번째로 가장 큰 값입니다!

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int p_parent[50005][25];  // parent[x][y] means 2^yth parent of x
int p_cost[50005][25];
int s_cost[50005][25];
int visit[50005];
int lv[50005];

// for lca
vector<pair<int, int>> adj[500005];   //<to,cost>

int ride_LCA(int a, int b, int p_parent[][25], int* lv, int p_cost[][25], int s_cost[][25], int no)
{
    int ret = -1;
    // diffrent level
    if (lv[b] < lv[a])
    {
        int temp = b;
        b = a;
        a = temp;
    }
    int ta=a;
    int tb=b;

    int diff1 = lv[b] - lv[a];
    int power1 = 0;
    while (diff1 != 0)
    {
        if (diff1 % 2 == 1)
            b = p_parent[b][power1];
        power1++;
        diff1 /= 2;
    }
    power1--;
    if (no != p_cost[tb][power1])
        ret = max(ret, p_cost[tb][power1]);
    if(no != s_cost[tb][power1])
        ret = max(ret, s_cost[tb][power1]);

    // now same level
    if (a == b)
        return ret;

    int now = 17;
    int g = 0;
    int tta=a;
    int ttb=b;
    while (-1 < now)
    {
        if (p_parent[a][now] != -1 && p_parent[a][now] != p_parent[b][now])
        {
            a = p_parent[a][now];
            b = p_parent[b][now];
        }
        if (p_parent[a][now] != -1 && p_parent[a][now] == p_parent[b][now])
            g = now;
        now--;
    }

    if (p_cost[tta][g] != no)
        ret = max(ret, p_cost[tta][g]);
    if(s_cost[tta][g] != no)
        ret = max(ret, s_cost[tta][g]);
    if (p_cost[ttb][g] != no)
        ret = max(ret, p_cost[ttb][g]);
    if(s_cost[ttb][g] != no)
        ret = max(ret, s_cost[ttb][g]);

    if(ret==0)
        return -1;
    return ret;
}

int Find(int* parrent, int num)
{
    if (parrent[num] == num)
        return num;
    return parrent[num] = Find(parrent, parrent[num]);
}

void Union(int* parrent, int num1, int num2)
{
    int p1 = Find(parrent, num1);
    int p2 = Find(parrent, num2);

    if (p1 <= p2)
        parrent[p2] = p1;
    else
        parrent[p1] = p2;
    return;
}


int main(int argc, char* argv[])
{
    int n, m;
    scanf("%d %d", &n, &m);

    int* arr = new int[n + 1];
    int* parrent = new int[n + 1];
    int* depth = new int[n + 1];
    for (int i = 0; i <= n; i++)
        parrent[i] = i;

    vector<pair<int, pair<int, int>>> E;  // <cost<from,to>>
    queue<int> not_use;
    vector<int> use;

    // Input
    for (int i = 0; i < m; i++)
    {
        int from, to, cost;
        scanf("%d %d %d", &from, &to, &cost);
        E.push_back(make_pair(cost, make_pair(from, to)));
    }
    sort(E.begin(), E.end());

    long long ans = 0;
    int count = 0;

    // Solve
    for (int i = 0; i < m; i++)
    {
        int from, to, cost;
        from = E[i].second.first;
        to = E[i].second.second;
        cost = E[i].first;

        int p1 = Find(parrent, from);
        int p2 = Find(parrent, to);
        if (p1 != p2)
        {
            Union(parrent, from, to);
            adj[from].push_back(make_pair(to, cost));
            adj[to].push_back(make_pair(from, cost));
            use.push_back(i);
            ans += cost;
            count++;
        }
        else
            not_use.push(i);
    }
    //printf("mst is : %d\n", ans);

    /////////////////////////////////// there is no MST
    if (n - 1 != count)
    {
        printf("-1\n");
        return 0;
    }

    ///////////////////////////////////////////////////////////////// setting lca

    visit[1] = 1;
    p_parent[1][0] = -1;
    lv[1] = 1;
    queue<int> Q;

    Q.push(1);
    while (!Q.empty())
    {
        int now = Q.front();

        Q.pop();
        for (int a = 0; a < adj[now].size(); a++)
            if (visit[adj[now][a].first] == 0)
            {
                visit[adj[now][a].first] = 1;
                p_parent[adj[now][a].first][0] = now;
                p_cost[adj[now][a].first][0] = adj[now][a].second;
                s_cost[adj[now][a].first][0] = -1;
                lv[adj[now][a].first] = lv[now] + 1;
                Q.push(adj[now][a].first);
            }
    }

    for (int i = 1; i <= 20; i++)
        for (int j = 1; j <= n; j++)
        {
            p_cost[j][i] = max(p_cost[j][i], p_cost[j][0]);
            //printf(":::::::p_cost[j][i] : %d p_cost[p_parent[j][i - 1]][i - 1] : %d s_cost[j][i] : %d\n", p_cost[j][i], p_cost[p_parent[j][i - 1]][i - 1], s_cost[j][i]);
            
            if(p_cost[j][i] < p_cost[j][i-1])
            {
                s_cost[j][i] = p_cost[j][i];
                p_cost[j][i] = p_cost[j][i-1];
            }
            if(p_cost[j][i] < p_cost[p_parent[j][i - 1]][i - 1])
            {
                s_cost[j][i] = p_cost[j][i];
                p_cost[j][i] = p_cost[p_parent[j][i - 1]][i - 1];
            }
            p_cost[j][i] = max(p_cost[j][i], p_cost[j][i-1]);
            p_cost[j][i] = max(p_cost[j][i], p_cost[p_parent[j][i - 1]][i - 1]);
            //printf("\nnow i:%d j:%d p_cost[j][i] is %d s_cost[j][i] is %d\n", i, j, p_cost[j][i], s_cost[j][i]);
            p_parent[j][i] = p_parent[p_parent[j][i - 1]][i - 1];
        }
    /////////////////////////////////////////////////////////////// setting is finish

    long long ANS = 9e20;
    while (!not_use.empty())
    {
        int NE = not_use.front();
        not_use.pop();

        int ncost = E[NE].first;              // big val
        int nfrom = E[NE].second.first;
        int nto = E[NE].second.second;
        //printf("===============start %d-%d\n", nfrom, nto);


        int lca = ride_LCA(nfrom, nto, p_parent, lv, p_cost, s_cost, ncost);
        //printf("find val is %d original is %d\n", lca,ncost);
        if (lca == -1)
            continue;
        ANS = min(ANS, ans - lca + ncost);
    }

    if (ANS != 9e20)
        printf("%lld\n", ANS);
    else
        printf("-1\n");
    return 0;
}

gun1120 1년 전 1

가중치가 0인 경우도 있습니다.

그리고 ride_LCA함수에서 정점 a,b의 레벨을 맞춰주는 과정과 레벨을 맞춘 후 lca를 찾는 과정에서
2ⁱ부모로 점프하는 게 있는데 점프할 때마다 값을 갱신해줘야 합니다.

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

문제

문제

출처

ICPC

살려주세요 SMST를 못이기고 있습니다

jin8431 1년 전 1

gun1120 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말