Fermé

Graph Teory problem | Problema de teoria dos grafos - C language

I want a solution of this problem in C language

Data de entrega: sexta, 22 Out 2021, 23:59

Número máximo de arquivos: 1

Tipo de trabalho: Trabalho individual

Museu

O Musée d’Orsay é um importante museu francês. Seus corredores estão repletos de belíssimas e importantíssimas obras de arte. Repleto de bens não fungíveis e valiosíssimos, a segurança do museu precisa ser eficiente e indefectível. E o novo diretor do Musée d’Orsay, Françoise Cachin, sabe disso. Por isso, Françoise pretende implantar um novo esquema de segurança no museu: ele pretende colocar seguranças nas junções dos corredores de tal forma que todo corredor seja vigiado. Todo corredor tem exatamente duas junções e um segurança parado em uma consegue vigiar todos os corredores daquela junção. Além de posicionar os seguranças de forma que todo corredor seja vigiado, o novo diretor quer fazer isso de forma que cada corredor seja vigiado por exatamente um segurança (ele sabe que se dois ou mais seguranças estão guardando um mesmo corredor, esses tendem a abandonar seus postos para conversar).

Como é o caso de todo museu nesse mundão véio, a grana anda curta e Françoise precisa implementar esse novo esquema de vigilância usando o menor número de seguranças possível. Como ele está tendo dificuldades em alocar os seguranças às junções e, para falar a verdade, ele nem sabe se tal tarefa é possível, ele decidiu contratar você, um famoso especialista em algoritmos, para realizar esse job.

Critérios importantes

Independente dos resultados dos testes o não cumprimento dos critérios abaixo implicará em nota zero para esta atividade. Qualquer dúvida, entre em contato.

Você deve resolver esse problema usando grafos que devem ser representados por matrizes de adjacências.

Observações

Você deve incluir, no início do seu programa, uma breve cabeçalho contendo no mínimo o seu nome e RA.

Indente corretamente o seu código e inclua comentários no decorrer do seu programa.

Linguagens aceitas: C

Entrada

A primeira linha da entrada consiste de dois inteiros n m, onde 1 <= n <= 1000 e 0 <= m <= n(n - 1)/2, representando o número de junções e o número de corredores, respectivamente. Cada junção é representada por um código numérico entre 0 e n - 1. Cada uma das próximas m linhas consiste de um par de inteiros u v, separados por espaço, onde 0 <= u, v <= n - 1, que representa a existência de um corredor conectando as junções de códigos u e v.

Saída

A resposta do seu programa deve consistir de um único inteiro z, representando o número mínimo de seguranças necessários no esquema de vigilância idealizado por Françoise, caso isso seja possível, ou da palavra IMPOSSIVEL, caso contrário.

Exemplos

Teste 01

Entrada:

8 3

0 7

1 7

4 7

Saída:

1

Teste 02

Entrada:

6 5

1 3

1 4

2 3

2 5

3 4

Saída:

IMPOSSIVEL

Teste 03

Entrada:

10 11

0 8

0 9

1 6

1 8

1 9

2 7

2 8

3 5

3 6

3 7

3 8

Saída:

4

I attached statements in english

Compétences : Programmation C

En voir plus : scheduling use graph colouring problem java, robust graph coloring problem forum, solving graph coloring problem using genetic programming code, project graph coloring problem, assignment problem in c language, graph in c language, graph theory problem, travelling salesman problem using genetic algorithm in c, travelling salesman problem using genetic algorithm in c++, graph coloring problem example, travelling salesman problem using dynamic programming in c, assignment problem using brute force in c, problem 12 project euler in c#, activity selection problem dynamic programming code in c, dining philosophers problem in os program in c, josephus problem using linked list in c++, 0-1 knapsack problem using dynamic programming in c, 8 puzzle problem using a* algorithm in c++, problem solving techniques in c language, reader writer problem using shared memory in c

Concernant l'employeur :
( 0 commentaires ) São Paulo, Brazil

Nº du projet : #31849038

1 freelance fait une offre moyenne de $20 pour ce travail

DaniilLakman

Dear sir! I'd like to express my interesting about your project. I have developed and executed strategies that I believe will bring value to you. I handled tasks very similar to what you outlined in your project. With Plus

%bids___i_sum_sub_35% %project_currencyDetails_sign_sub_36% USD en 2 jours
(3 Commentaires)
2.8