16562) 친구비

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

struct pengyou
{
int cost;
struct pengyou * link;
int visit;
};

int find(struct pengyou* arr, int tomo)
{
if (arr[tomo].visit < 0)
return tomo;

int zzin_tomo = find(arr, arr[tomo].visit);
arr[tomo].visit = zzin_tomo;

return zzin_tomo;
}

void merge(struct pengyou* arr, int tomo1, int tomo2)
{
if (arr[tomo1].cost < arr[tomo2].cost)
arr[tomo2].visit = find(arr, tomo1);

else
arr[tomo1].visit = find(arr, tomo2);
}

int main()
{
int number, relation, money;
scanf("%d %d %d", &number, &relation, &money);

struct pengyou* arr;
arr = (struct pengyou*)malloc(sizeof(struct pengyou)*number);

for (int i = 0; i < number; i++)
{
scanf("%d", &arr[i].cost);
arr[i].visit = -1;
}

int tomo1, tomo2;
for (int i = 0; i < relation; i++)
{
scanf("%d %d", &tomo1, &tomo2);

tomo1--;
tomo2--;
int zin_tomo1 = find(arr, tomo1);
int zin_tomo2 = find(arr, tomo2);

if (zin_tomo1 == zin_tomo2)
{
continue;
}

merge(arr, zin_tomo1, zin_tomo2);
}

int nedan = 0;
for (int i = 0; i < number; i++)
{
if (arr[i].visit < 0)
nedan += arr[i].cost;
}

if (nedan <= money)
printf("%d\n", nedan);
else
printf("Oh no");

free(arr);

return 0;
}

///////////////////////////////////////////////////////

int main()
{
int number, relation, money;
scanf_s("%d %d %d", &number, &relation, &money);

struct pengyou* arr;
arr = (struct pengyou*)malloc(sizeof(struct pengyou)*number);
for (int i = 0; i < number; i++)
{
scanf_s("%d", &arr[i].cost);
arr[i].link = NULL;
arr[i].visit = 0;
}

int tomo1, tomo2;
for (int i = 0; i < relation; i++)
{
scanf_s("%d %d", &tomo1, &tomo2);
tomo1--;
tomo2--;
if (arr[tomo1].cost > arr[tomo2].cost)
{
if (arr[tomo1].visit == 1)
{
struct pengyou * temp1 = malloc(sizeof(struct pengyou));
temp1->link = &arr[tomo1];
struct pengyou * temp2 = malloc(sizeof(struct pengyou));
temp2->link = &arr[tomo2];
while (temp1->link->link != NULL)
{
temp1->link = temp1->link->link;
}

while (temp2->link->link != NULL)
{
temp2->link = temp2->link->link;
}

temp1->link->link = temp2->link;
temp1->link->visit = 1;

}

else
{
arr[tomo1].link = &arr[tomo2];
arr[tomo1].visit = 1;
arr[tomo1].cost = arr[tomo2].cost;
}
}

else
{
if (arr[tomo2].visit == 1)
{
struct pengyou * temp1=malloc(sizeof(struct pengyou));
temp1->link = &arr[tomo1];
struct pengyou * temp2 = malloc(sizeof(struct pengyou));
temp2->link = &arr[tomo2];
while (temp1->link->link != NULL)
{
temp1->link = temp1->link->link;
}

while (temp2->link->link != NULL)
{
temp2->link = temp2->link->link;
}

temp2->link->link = temp1->link;
temp2->link->visit = 1;
}

else
{
arr[tomo2].link = &arr[tomo1];
arr[tomo2].visit = 1;
arr[tomo2].cost = arr[tomo1].cost;
}
}
}

int nedan=0;
for (int i = 0; i < number; i++)
{
if (arr[i].visit == 0)
{
nedan += arr[i].cost;
}
}


if (nedan <= money)
printf("%d\n", nedan);
else
printf("Oh no");

free(arr);

system("pause");
return 0;
}

///////////////////////////////////////////////////////

union 문제

위의거는 전형적인 유니온 형식으로 풀었고

아래거는 내가 직접 짜본 알고리즘이다.

내가 직접 짠 것은 비효율적이다. 문제 시간 초과로 나옴.

visit을 0과 1로 나눈 다음, 방문한 것 중 큰 값은 1로 처리.

이미 1인 것을 방문 시, 이는 곧 쓸데없는 연결을 의미하므로,

visit==1일 때의 예외처리를 한다.

이때, tomo1과 tomo2 각각의 가장 끝 노드, link=NULL일 때까지 while처리를 한다.

이렇게 나온 것들의 cost를 다시 비교해, 적절하게 union 처리를 한다.

 

변수명이 갈수록 이상해진다.

일어변수명 nedan(가격), tomo(친구)

중국어변수명 pengyou(친구)