编程介的小学生 2019-10-04 18:02 采纳率: 20.5%
浏览 64

Cattle 具体的代码

Description

A group of more or less domesticated bovine animals (hereafter to be referred to as cattle) are to be loaded into railway freight cars of certain train. The train consists of K freight cars (and a locomotive, which is kind of irrelevant to this problem), which can be loaded with at most M animals each. A number from 1 to N is painted on each animal (all numbers are used and no two animals carries the same number so by easy induction on N one concludes that there are exactly N animals).

The animals are patiently waiting to be loaded in a queue sorted by their numbers in ascending order (1 is the first to be loaded etc.). One freight car is loaded at a time by arbitrary number of animals (not exceeding M, of course) from the beginning of the queue and then locked so no subsequent load of animals to that freight car is possible. The process of loading is continued until all freight cars are locked.

It is known that some clashing pairs of animals dislikes each other and if loaded in the same freight car then the stronger one will attempt to kill the other. It is also known that there are friendly pairs of animals where the stronger animal will always successfully protect the weaker one from attack of any other animal. If no alive friendly protecting animal is present, the attack of stronger animal of a clashing pair is always successfull. All attacks in a freight car starts when it is locked. The transportation lasts long enough for all attacks to finish.

Write a program that will suggest the loading of animals to the freight cars so that the number of alive animals at the end of transportation will be as large as possible.
Input

The first line of the input contains three integers N, K, M; 1 <= N,K <= 1000, 1 <= M <= 20. The second line contains integer D – the number of clashing pairs among the animals.

Each of the following D lines contains three mutually different integers A, B, C. The pair (A, B) represents a clashing pair, and the pair (C, B) represents a friendly pair of animals. The second animal in each pair is always the weaker one.

A stronger animal of a clashing pair cannot be a weaker animal in any other pair (the first number A cannot occur as a second number anywhere). A weaker animal of a clashing pair has exactly one friendly protecting animal (the third number C is uniquely determined by the first two numbers A and B).
Output

The first and only line of the output consists of an integer – the maximal number of alive animals at the end of transportation.
Sample Input

5 2 3
2
1 2 3
1 3 2
Sample Output

5

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
    • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
    • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
    • ¥30 3天&7天&&15天&销量如何统计同一行
    • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
    • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
    • ¥15 vs2019中数据导出问题
    • ¥20 云服务Linux系统TCP-MSS值修改?
    • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
    • ¥20 怎么在stm32门禁成品上增加查询记录功能