b359: [福州19中]电路图
Tags : 模拟
Accepted rate : 1人/2人 ( 50% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-30 08:52

Content

    小D刚学了怎么画电路图,由于他学的不太认真,所以还是不会做作业,那么他就把作业交给你了。

众所周知,电路图有串联和并联。如下图所示:

         图1  串联电路                   图2  并联电路

现在,老师布置了作业:给出一个电路图,判断这个电路图是串联还是并联,并且判断由S控制的灯泡的数量,并按字典序输出这些灯泡的编号(开关只有1个,灯泡可能不只一个)

    下面解释一下串联和并联:串联指的是多个灯泡首尾顺次相接连到一起,如左图,L1L2串联;并联指的是多个灯泡首接首,尾接尾,连入电路中,如右图,L1L2并联。

Input

电路图的输入方法:

第一行,3个数,nmk,表示n个部件和m个端点,k条导线。

2~n+1行,每行3个数,分别表示原件的名称及它左右端点的编号。

接下来k行,每行2个数,a, b,表示导线从端点a连到端点b

注意:

①为了简化问题,电路图中只可能有3种原件,分别为电源(符号P),开关(符号S),灯泡(灯泡的标号问题在下面会有明确阐释)

②有些端点是无用的,在样例中会有解释。

③每条导线只能连接2个端点。且电流可逆。

④保证不出现电路故障,比如短路、开路。

⑤灯泡没有规定要按照顺序编号,可以完全不按顺序,如L3L5(编号不超过100000)

⑥选手不需要考虑并联里有串联或串联里有并联,也可以不需要考虑并联里再加并联时开关在一条支路的干路上。如下图,这样的情况是不允许的。

不允许电路图的部分

Output

 共2行,第一行,两个数,第一个数表示串联还是并联,串联输出1,并联输出0;第二个数表示由S控制的灯泡的数量。第二行,若干个符号,表示由S控制的灯泡的符号(如L1L2,……)请按输入中所给顺序输出

Sample Input
样例1:          //此行在测资中没有
4 10 7
P 1 2
S 3 4
L1 5 6
L2 7 8
1 10
10 7
10 5
7 9
5 9
9 4
2 3
样例2:          //此行在测资中没有    
4 9 5
P 3 4
S 1 2
L1 7 8
L2 5 6
3 7
8 5
6 9
9 2
4 1
Sample Output
样例1:          //此行在测资中没有
0 2
L1 L2
样例2:          //此行在测资中没有
1 2
L1 L2
測資資訊:
記憶體限制: 128 MB
公開 測資點#0 (1%): 1.0s , <1K
公開 測資點#1 (1%): 1.0s , <1K
公開 測資點#2 (3%): 1.0s , <1K
公開 測資點#3 (3%): 1.0s , <1K
公開 測資點#4 (3%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1K
公開 測資點#7 (5%): 1.0s , <1K
公開 測資點#8 (5%): 1.0s , <1K
公開 測資點#9 (6%): 1.0s , <1K
公開 測資點#10 (6%): 1.0s , <1K
公開 測資點#11 (6%): 1.0s , <1K
公開 測資點#12 (6%): 1.0s , <1K
公開 測資點#13 (6%): 1.0s , <1K
公開 測資點#14 (6%): 1.0s , <1K
公開 測資點#15 (6%): 1.0s , <1K
公開 測資點#16 (6%): 1.0s , <1K
公開 測資點#17 (6%): 1.0s , <1K
公開 測資點#18 (6%): 1.0s , <1K
公開 測資點#19 (9%): 1.0s , <1K
Hint :

本题共有20个测资(测试点),每一个测试点分数不平均分配

为了减小这题的难度,我们约定:

①对于2%的测资,为样例数据。

②对于9%的测资,所给的输入均为题干中所示的串联电路图m<=15k<=m

③对于20%的测资,所给的输入均为题干中所示的并联电路图m<=20k<=m

注意:原件位置可能有所调整!

④对于60%的测资,不保证是否存在多余的点,所给输入不保证均为题干中所示电路图,n<=6, m<=30k<=m

⑤对于最后9%的测资,存在多余的点,且所给测资肯定不是题干中已有图,n<=10,m<=50,k<=m.

⑥测资及分数对应关系如下:

测资

1~2

3~5

6~9

10~19

20

总共

每测资分数

1

3

5

6

9

\

总分数

2

9

20

60

9

100

 

 

【数据解释】

样例1:可画出如下图:

样例解释1

易得:为并联,且S闭合时L1L2都亮。

样例2

样例解释2

易得:为串联,且S闭合时L1L2都亮。

 

 

Tags:
模拟
出處:
Noip2014 RP++ Round 2 [管理者:
abs2000 (重回zerojudge立志刷榜1)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」