当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

1378:Power Cable Problem

题目描述
The downtown of city T consists of N, 1 <= N <= 10000, tall commercial buildings that have basements. The buildings are numbered from 0 through N-1. The electricity of each building is provided by the City Electrical Power Company that puts all of its M, 1 <= M <= 50, power cables underground. In order for a building to have electricity, a power line must be connected from one of the underground cables to a power converter inside the building. Because of technical reasons, each power cable is a loop, meaning that it is a long cable line that originates from a mini power station, runs through some regions in the city and then comes back to the same power station. It is known that each power cable connects to at least 2 and at most 500 buildings. A building may be connected to zero, one or more than one power cable. The electricity of a building connected to more than one power cable can be provided by any one power cable by properly setting its power converter. To have a better city view, it is required by the law that power converters can only be built inside the basements.

During a Typhoon, the local rain storm, the downtown of city T is flooded. The basements of K, 1 <= K <= N, buildings are filled with water. Fortunately, none of the mini power stations are damaged. Once a basement is flooded with rain water, its power converter is damaged and the building is out of electricity. Before fixing the power converter, we need to drain the water in the basement, which takes at least a long time. To make the situation worse, the power cables of city T are designed with the constraint that for each power cable, if it is connected with a damaged power converter, then none of the power converters connected to this power cable can be turned on. It is also impossible to disconnect the damaged power converts from the power cables. However, it is possible to properly set a power convert to get electricity from a power cable that carries electricity. After Typhoon, the City Electrical Power Company needs to know the total number of buildings that are out of electricity. Since the flood has made the traffics inside the city bad, the company cannot send people to survey. Fortunately, it is known by the company the buildings that are flooded in Typhoon since people from those buildings telephoned the company for help. Giving the original power line connection oor plans and the buildings that are flooded, your task is to calculate the total number of buildings that are currently out of electricity, including the ones that are originally not connecting to any power cable.
For example, each circle in Figure 1 represents a building. Two concentric circles represents a flooded building. There are 9 buildings. Buildings 7 and 8 are flooded. Solid straight lines are power cables. There are 3 power cable lines. One connects buildings 0, 1 and 6. One connects buildings 1, 2, 3 and 7. The last one connects buildings 0, 1, 4, 5 and 8. Buildings 2, 3, 4, 5, 7 and 8 do not have electricity currently in this example.


输入解释
The input file consists of several test cases. In each test case, the first line consists of three integers N, M and K separated by a single space. Each of the following M lines represents in a power cable by beginning with the number of buildings in this power cable and then a list of buildings in this cable in clockwise order. It then followed by a line of K integers, each separated by a space, representing the buildings that are flooded. A line with three 0's separates two test cases. The end of the file is a line with three -1's.
输出解释
For each test case, output the total number of buildings that are out of electricity in a line.
输入样例
9 3 2
3 0 1 6
4 1 7 3 2
5 0 4 5 8 1
7 8
0 0 0
5 2 1
3 0 2 1
3 1 4 3
4
-1 -1 -1
输出样例
6
2 

该题目是Virtual Judge题目,来自 北京大学POJ

题目来源 Taiwan 2001

源链接: POJ-1378

最后修改于 2020-10-29T06:02:27+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
1000 10000