2 shunfurh shunfurh 于 2017.01.01 14:15 提问

Failing Roads
it

Description

There are n towns in the kingdom of Failland. In the past, Failland used to have an excellent system of roads, connecting each town directly to each other, without any two roads crossing -- they used a complicated system of bridges to ensure this. Recently, however, the Road-workers Union split into n independent divisions, one for each town. Due to a huge aversion between divisions, each division strictly refuses to maintain roads that lead to a town controlled by any other division. Since initially each division controlled one town only, all of the roads were soon completely broken.

The wise king of Failland has decided to improve the situation using decrees. In several decrees, he ordered some of the divisions to unite again. Whenever road-workers received such a decree, they obeyed (Well, wouldn't you obey the order when the only other option was to have your head chopped off?) and the divisions in concern were immediately united into a single one. But since the workers are lazy and the decree did not explicitely say otherwise, the union process did not affect the roads being maintained. The united division still maintained only those roads that it used to maintain before.

Therefore, the king started to issue another type of decrees, saying that the road workers of some division must immediately repair all of the destroyed roads between the towns the division controls. He then repeated the whole process of uniting the divisions and ordering them to work several times, and finally, when only one united division remained, he considered the problem solved and went for a vacation.

However, citizens of Failland soon noticed that there is still something wrong, and that there are too few roads. After some research, they found out that whenever the workers of a division accepted an order to repair all of the destroyed roads, they also automatically supposed that they can stop maintaing the roads they maintained before, and such roads decayed quickly.

In order to persuade the king to return from the vacation and to solve the problem somehow, citizens have decided to find as many towns as possible such that no two of them are connected by a direct repaired road. They plan to send this list to the king because they feel it could help somehow. However, this task turned out to be too difficult, thus they decided to ask you for help.
Input

The input consists of several scenarios. Each scenario consists of a single line. This line contains an expression that describes the sequence of king's decrees, and hence also the current state of the roads in Failland. The expression is one of the following:
V stands for a single town controlled by a single division.
U e1 e2, where e1 and e2 are expressions. The expressions e1 and e2 correspond to disjoint sets of towns, each of the sets is under control of a different division of road-workers. The expression U e1 e2 describes the situation after the king ordered these divisions to unite, i.e., the new united division now controls all the towns in e1 and e2, and maintains still the same set of roads (the union of the roads maintained before, as described by e1 and e2).
C e, where e is an expression. This expression describes the situation after the division described by e received the order to take care of the roads they neglected so far. The division still controls the same set of towns, but now maintains exactly those roads they did not maintain before the order was received. Of course, only the roads connecting two towns both controlled by the same division are concerned. The roads they used to maintain before are not maintained anymore and are considered destroyed immediately.
For example, "C U U V V V" describes the land with three towns controlled by a single union, and with all three roads between these towns in a perfect condition, forming a triangle. The expression "U C U U V V V C U U V V V" describes the land with six towns formed as a union of two such triangles. The expression "C U C U U V V V C U U V V V" describes the same land after the decree that orders road-workers to repair the neglected roads. Now the land has six towns and 9 roads -- all of the roads between all pairs of towns, except for those six that belonged to the triangles.

Each line of the input contains at most 200 000 characters.
Output

The output for each scenario consists of a single line containing a single integer -- the maximum number of towns such that no two of them are connected by a maintained road.
Sample Input

U V V
U C U V V V
C U C U U V V V C U U V V V
Sample Output

2
2
3

1个回答

caozhy
caozhy   Ds   Rxr 2017.01.05 23:53
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
构筑极致用户体验-ROADs
通信世界网消息(CWW) 信息时代发展到今天,物理世界和数字世界正在加速融合,人类社会正发生着剧烈的改变,人类的情感、财富、知识、历史……正在加速从线下转移到线上,以“0101”的形式被发送、传送、接收、存储起来,人们随时随地可以接入到数字世界探索翱翔,新时代下的人类也被称为“数字元人”。同时数字经济正在改变和颠覆着传统市场格局,哺育了一个又一个新的市场和商业新浪潮,如工业4.0、物联网、大数据、
1087. All Roads Lead to Rome (30)【最短路】——PAT (Advanced Level) Practise
题目信息1087. All Roads Lead to Rome (30)时间限制200 ms 内存限制65536 kB 代码长度限制16000 B Indeed there are many different tourist routes from our city to Rome. You are supposed to find your clients the route with
Codeforces 543B. Destroying Roads 最短路+暴力
最短路+暴力,暴力BFS求任意两点间的短路,然后暴力枚举哪一段是公共的 B. Destroying Roads time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard
Consul小贴士-记一次Consul注册failing状态跟踪
前言最近抽了点时间基于最新的Consul1.0.2构建了集群,替换了原来的0.9.2服务。结果在启动基于SpringCloud D版的服务时所有节点的health状态均为DOWN,瞬间一切都不好了,本章记录如何进行坑点的排查并解决的过程,提供一个源码阅读的思路。本章概要1、场景描述;2、源码分析;场景1、首先看到如下config-server服务处于failing状态:2、通过其health端点即...
【PAT】1087. All Roads Lead to Rome (30)
Indeed there are many different tourist routes from our city to Rome. You are supposed to find your clients the route with the least cost while gaining the most happiness. Input Specification: E
HDU 1301 &POJ 1215 Jungle Roads【最小生成树,Prime算法+Kruskal算法】
Jungle Roads Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 6737    Accepted Submission(s): 4893 Problem Description The Head
Codeforces Good Bye 2017 F - New Year and Rainbow Roads
一、如果升序中没有G颜色点: 那么我们找到第一个B颜色点prb(prev-blue)和最后一个B颜色点sub(succ-blue),和第一个R颜色点prr(prev-red)和最后一个R颜色点suc(succ-red),最优的方案是: cost=xsub−xprb+xsur−xprrcost=x_{sub}-x_{prb}+x_{sur}-x_{prr} 如果某个颜色也不存在,则记Δx=0。二
Codeforces 543B Destroying Roads 【暴力 SPFA】
B. Destroying Roads time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output In some country there are exactly n cit
POJ-2421-Constructing Roads(最小生成树 普利姆)
D - Constructing Roads Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u SubmitStatusPracticePOJ 2421 Description There are N villages, which are numbered from 1 to N, an
Lightoj1002——Country Roads(最短路变形)
I am going to my home. There are many cities and many bi-directional roads between them. The cities are numbered from 0 to n-1 and each road has a cost. There are m roads. You are given the number of m