22737_StrangeRegulations

2022-5-16 18:22| 发布者: Hocassian| 查看: 23| 评论: 0|原作者: 肇庆学院ACM合集

摘要:
C:\Users\Administrator\Downloads\2019-10-12-10-14-5-89506909886200-Problem List-采集的数据-后羿采集器.html

Pro.ID

22737

Title

Strange Regulations

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=22737

AC

2

Submit

8

Ratio

25.00%

时间&空间限制

  • Time Limit: 40000/20000 MS (Java/Others)     Memory Limit: 131072/65536 K (Java/Others)
  • 描述

    Thank to cryptography, we are able to encrypt messages such that noone (except the intended recipient) is able to read them. However, encrypted messages are of no use if they do not actually reach the recipient. These days, computer network is the most typical mean to send such messages. In this problem, we will study the issues the networking providers have to solve. And remember: since the message is encrypted, we do not need to care about the network privacy anymore.

    The network cables joining computers (servers) belong to different companies. A new antimonopoly legislation prevents any company from owning more than two cables from each server. Furthermore, to avoid wasting resources, there is also a law specifying that the cable system owned by any single company cannot be redundant, i.e., removal of any of the cables will disconnect some two previously connected servers. Since the companies buy and sell the cables all the time, it is quite difficult to enforce these regulations. Your task is to write a program that does so.

    输入

    The input contains several instances. The first line of each instance contains four integers N, M, C and T separated by spaces — the number of servers (1 ≤ N ≤ 8000), the number of cables (0 ≤ M ≤ 100000), the number of companies (1 ≤ C ≤ 100), and the number of cable-selling transactions (0 ≤ T ≤ 100000), respectively.

    The following M lines describe the cables. Each of them contains three integers Sj1, Sj2 and Kj , separated by spaces, giving the numbers of the servers Sj1 and Sj2 (1 ≤ Sj1 < Sj2N) joined by that cable and the number of the company Kj (1 ≤ KjC) initially owning the cable. For each pair of servers, there is at most one cable joining them. The initial state satisfies the regulations, i.e., each company owns at most two cables incident with each server, and the system of cables owned by a single company has no cycles.

    Finally, each of the next T lines contains integers Si1, Si2 and Ki describing one transaction in which the company Ki (1 ≤ KiC) tries to buy a cable between servers Si1 and Si2 (1 ≤ Si1 < Si2N).

    The last instance is followed by a line containing four zeros.

    输出

    Description

    Thank to cryptography, we are able to encrypt messages such that noone (except the intended recipient) is able to read them. However, encrypted messages are of no use if they do not actually reach the recipient. These days, computer network is the most typical mean to send such messages. In this problem, we will study the issues the networking providers have to solve. And remember: since the message is encrypted, we do not need to care about the network privacy anymore.

    The network cables joining computers (servers) belong to different companies. A new antimonopoly legislation prevents any company from owning more than two cables from each server. Furthermore, to avoid wasting resources, there is also a law specifying that the cable system owned by any single company cannot be redundant, i.e., removal of any of the cables will disconnect some two previously connected servers. Since the companies buy and sell the cables all the time, it is quite difficult to enforce these regulations. Your task is to write a program that does so.

    Input

    The input contains several instances. The first line of each instance contains four integers N, M, C and T separated by spaces — the number of servers (1 ≤ N ≤ 8000), the number of cables (0 ≤ M ≤ 100000), the number of companies (1 ≤ C ≤ 100), and the number of cable-selling transactions (0 ≤ T ≤ 100000), respectively.

    The following M lines describe the cables. Each of them contains three integers Sj1, Sj2 and Kj , separated by spaces, giving the numbers of the servers Sj1 and Sj2 (1 ≤ Sj1 < Sj2N) joined by that cable and the number of the company Kj (1 ≤ KjC) initially owning the cable. For each pair of servers, there is at most one cable joining them. The initial state satisfies the regulations, i.e., each company owns at most two cables incident with each server, and the system of cables owned by a single company has no cycles.

    Finally, each of the next T lines contains integers Si1, Si2 and Ki describing one transaction in which the company Ki (1 ≤ KiC) tries to buy a cable between servers Si1 and Si2 (1 ≤ Si1 < Si2N).

    The last instance is followed by a line containing four zeros.

    Output

    For each input instance, output T lines describing the outcome of the transactions. The possible outcomes are

    • "No such cable." if the pair of servers is not joined by a cable,

    • "Already owned." if the cable is already owned by the company Ki,

    • "Forbidden: monopoly." if the company Ki already owns two cables at Si1 or Si2,

    • "Forbidden: redundant." if Ki owns at most one cable at each of Si1 and Si2, but granting the ownership would create a cycle of cables owned by Ki,

    • "Sold." if none of the above restrictions apply. In this case, the ownership of the cable between Si1 and Si2 changes to Ki for the purpose of further transactions.

    Print one empty line after each instance.

    Sample Input

    4 5 3 5
    1 2 1
    2 3 1
    3 4 2
    1 4 2
    1 3 3
    1 2 3
    1 2 3
    1 4 3
    2 3 3
    2 4 3
    2 1 1 1
    1 2 1
    1 2 1
    0 0 0 0

    Sample Output

    Sold.
    Already owned.
    Forbidden: monopoly.              
    Forbidden: redundant.
    No such cable.

    Already owned.

    Source

    样例输入

    4 5 3 5
    1 2 1
    2 3 1
    3 4 2
    1 4 2
    1 3 3
    1 2 3
    1 2 3
    1 4 3
    2 3 3
    2 4 3
    2 1 1 1
    1 2 1
    1 2 1
    0 0 0 0

    样例输出

    Sold.
    Already owned.
    Forbidden: monopoly.              
    Forbidden: redundant.
    No such cable.

    Already owned.

    提示

    作者


    路过

    雷人

    握手

    鲜花

    鸡蛋

    最新评论

    返回顶部