Блог пользователя PML

Автор PML, 14 лет назад, По-русски

Сегодня писал контест и там попалась вот такая задача:

Мэр города Гадюкино решил проверить состояние дорог после только что проведенного капитального ремонта. Для этого он хочет проехать по каждой дороге в обоих направлениях. Помогите мэру составить кратчайший маршрут, проходящий по каждой дороге в каждом направлении хотя бы один раз.

В городе Гадюкино n перекрестков и m дорог, каждая из которых соединяет два различных перекрестка. Между двумя перекрестками может быть не более одной дороги. Известно, что по дорогам от каждого перекрестка можно доехать до любого другого.

Входные данные
Входной файл содержит целые числа n и m (1 ≤ n ≤ 104, 1 ≤ m ≤ 105), и далее m пар целых чисел ai и bi - номера перекрестков, которые соединяет i-я дорога. 

Выходные данные
В выходной файл выведите число s - минимальную длину пути и далее s+1 число - номера перекрестков в том порядке, в котором их нужно проезжать.

Я получил по ней 90 баллов нахождением Эйлерова пути в ориентированном графе, но мне кажется, что это не я напортачил, а просто плохой алгоритм решения. Вообщем у кого какие идеи решения? Поделитесь.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится
Утверждается, что решение правильное.

Каждое ребро превращается в одно входящее и одно исходящее, поэтому входящаая и исходящая степень каждой вершины одинакова. Поэтому Эйлеров путь существует.

Рекомендую поискать ошибку в реализации. 

Например я не понял обязательно ли граф связен. Если нет, то вы могли потерять случай изолированных вершин и еще много чего. Например задавный, о не уверен, что допустимый тест.
3 1 2 3. Не умею читать.
14 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
Это задача D из седьмой личной олимпиады на acmp.ru. Я тоже решил её через Эйлеров путь со списками смежности. Вот моё решение:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<stdlib.h>
#include<math.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define FOR(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

int n,m,c=0,x,y,d[200001],h[200001],s[200001],ne[200001];

void dfs(int v)
 {
  int j=h[v];
  while (j!=0)
   {
    h[v]=0;
    dfs(s[j]);
    j=ne[j];
   }
  c++; d[c]=v;
 }

void read()
 {
  cin>>n>>m;
  For(i,1,m)
  {
   cin>>x>>y;
   s[i]=y;
   ne[i]=h[x];
   h[x]=i;

   s[i+m]=x;
   ne[i+m]=h[y];
   h[y]=i+m;
  }
 }

void solve()
 {
  dfs(1); // graf svyaznyi
 }

void write()
 {
  cout<<c-1<<endl;
  FOR(i,c,1) cout<<d[i]<<" ";
 }

int main()
{
 freopen("input.txt","r",stdin);
 freopen("output.txt","w",stdout);
  read();
  solve();
  write();
 return 0;
}
  • 6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Подскажите пожалуйста, где можно почитать про такой способ представления графа?

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Может быть у тебя из-за ограничении неправильно? Я в начале тоже маленькие ограничения сделал. Потом переправил ;)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Так ведь можно просто обойти граф в глубину из произвольной точки. При таком обходе каждое ребро, входящее в остовное дерево, проходится два раза - туда и обратно. Те ребра, которые не входят в остовное дерево, - обратные ребра мы сами проходим туда и обратно, если найдем их во время обхода в глубину.
Минимальная длина пути, насколько я понимаю, всегда будет равна 2*m.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я решал точно такую же задачу год назад.Там есть тесты либо без рёбер, либо с несвязным графом.Просмотри эти случаи.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Вот условие: В городе Гадюкино n перекрестков и m дорог, каждая из которых соединяет два различных перекрестка. Между двумя перекрестками может быть не более одной дороги. Известно, что по дорогам от каждого перекрестка можно доехать до любого другого.
      • 14 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        Известно, что по дорогам от каждого перекрестка можно доехать до любого другого.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Я как бы на это и намекал...в условии скорее всего неточность....
          Ещё попробуй стек расширить.