HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Graph problems and UF > problem:


51079 - Key person - 2

Guest
• Review clarifications (1)

Section problems

• 50414 - Traffic
• 50698 - Ayran Delivery
• 50978 - Albanian Coders
• 50699 - Fighting Vampires
• 50857 - Nine-Stones Game
• 50929 - Present from your uncles
• 51076 - Key person
• 51080 - Deepest Point
• 51079 - Key person - 2
• 50464 - From Tirana to Durres
• 50691 - The traveling salesman prob...
• 50701 - Cell Removal
• 50703 - The Shortest Path
• 50704 - Connected?
• 50705 - Student Clubs

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Ibrahim Mesecan.

Key person - 2

You have a company and you can get/buy friendship information from several internet companies. Now, you want to hire m people who has the greatest number of connections. If there are people with the same number of friends/connections, put them in ascending order according to their total relationship costs and ids.

Question: Write a program that will read e relationship information for n people. Then, it will find m people for your company.
Notes:

  1. The weight/length of relationship from one person to another is 1 if one knows the other (if person A knows person B and Person B knows Person C, then person A knows person C with the length of 2),
  2. Assume that length of self-relation is zero,
  3. If person A knows another (B), it does not mean that person B knows person A (the relationships are directed).
  4. Assume that if one person does not know another the distance between them is max (9999),

Input specification: You will be first given three integers:
  1. the number of people (n) and
  2. the number of relationships (e)
  3. the number of people to show (m)
Then in the following e lines, you will be given two integers:
  • ID of the person a: an integer between 1 and n
  • ID of the person b: an integer between 1 and n
which means a knows b; where 1 ≤ m ≤ n ≤ 200 and 0 ≤ e ≤ 10,000.

Output specification: Show m integers: the IDs (orders) of m people.

Sample Input Sample Output
7 12 3
1 2
1 4
2 4
3 1
3 6
4 3
4 5
4 7
5 2
5 7
4 6
7 6
4 1 2

Explanation: Person 1 knows Persons 2 and 4 directly. But he knows Persons 3, 5, 6, and 7 with a length of 2. So, Person 1 knows 6 people with a total distance of (0+1+2+1+2+2+2=)10. The table below shows the number of people they know and the total distance for those people.

Person ID People knows Total Distance
4 68
1 610
2 612
3 612
5 613
7 11
6 00


Для отправки решений необходимо выполнить вход.

www.contester.ru