BZPRO

#3081. [Cerc2011]Strange Regulations

内存限制：128 MiB 时间限制：10 Sec
提交 提交记录 讨论

题目描述

在一个计算机网络中，连接两台计算机的电缆属于不同的公司。一项新的反垄断法规定，一家公司连接同一台计算机的电缆不能超过两条。为了避免资源浪费，另外一条法律规定，一家公司的电缆系统不能有冗余，即去掉任意一个电缆之后，至少一对之前连通的计算机要断开连接。由于这些公司不断的销售和购入电缆，要确定他们是否遵守这些规则十分的困难。你的任务是写一个程序完成这个任务

输入格式

多组测试数据。第一行是4个整数N，M，C，T——计算机的数量1<=N=8000，电缆的数量0<=M<=100000，公司的数量1<=C<=100，电缆销售/购入的数量0<=T<=100000。
 接下来M行，每行三个整数Sj1,Sj2,Kj，代表这条电缆连接的两个服务器Sj1,Sj2以及电缆所属的公司Kj。初始状态是遵守规则的。
 接下来行，每行3个整数Si1,Si2,Ki，表示公司购入了连接S1,S2的电缆。
 4个0标志着测试文件的结束。

输出格式

对于每个测试数据，输出行：
         “No Such Cable.” 如果这对服务器之前没有被一对电缆相连
         “Already owned.” 如果这对电缆本来就属于这家公司
         “Forbidden: monopoly.” 如果公司Ki已经有2条电缆与S1或S2相连
         “Forbidden: redundant.” 如果公司Ki公司购入这条电缆后，会在其网络中形成环
         “Sold.” 操作成功

样例

样例输入


			
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.

数据范围与提示



        

BZPRO Powered by Remmina.
Github Repository