ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1160. Network

WA6
Послано SProf 16 фев 2016 17:19
i try to solve it with kruskal and it gives me wa6 can anyone help me?
Re: WA6
Послано c_pp 11 янв 2017 01:38

struct edge
{
   int len; int a; int b;
};

int rank[1024];
int parent[1024];
edge e[15008];
int n,m;
int get_parent(int x)
{
   if (x != parent[x])parent[x] = get_parent(parent[x]);
   return parent[x];
}

bool join_dsu(int x, int y){
      x = get_parent(x); y = get_parent(y);
     if (x == y) return false;
    if (rank[x] < rank[y]) parent[x] = y; else if (rank[x] > rank[y]) parent[y] = x;
    else parent[y] = x, ++rank[x];
  return true;
}

//  read edges
//  sort edges by len
//  p[i] = i, for i = 1..n
//  let l_min = 0;
//   i = 1..m
//   if (  join_dsu( e[i].a, e[i].b) ){ l_min = e[i].len; }
//  print l_min   and all edges where len <= l_min,  GOOD LUCK !!