Graph Discovery [交互题]没弄好
题目描述:
Bessie 准备了一个难题给Farmer Johm。在他面前是一个有N个岛屿的湖泊，岛屿之间有桥。 Bessie会告诉FJ如果不用一个桥的集合，是否可以从任意岛屿走到任意岛屿。 也就是说，我们考虑一张图。Bessie告诉FJ如果拿走一个边集，N个点是否还是连通的？（保证初始的图是连通的。） FJ想要知道哪些桥是存在的。你要用尽可能少的询问帮助FJ搞清楚这个问题。 下面是一个例子：
1--2
|\ |
| \|
4 3
FJ 的询问 | Bessie 的回答 |
------------------------------------------------------------------------
{{1,2}} | Yes |
{{3,4}} | Yes |
{{1,4}, {4,3}} | No | {1,4} 肯定是边
{{1,2}, {2,3}} | No | {2,3} 肯定是边
{{1,2}, {3,1}} | No | {1,3} 肯定是边
{{1,3}} | Yes | {1,2} 肯定是边
{{1,4}} | No | {2,4} 和 {3,4} 肯定不是边
FJ就可以搞明白，原图的边集是 {{1,2}, {1,3}, {1,4}, {2,3}}。
这个问题是一个交互题，也就是说，你不使用读入和写入文件，而是采用stdin和stdout来和一个程序交互。详见下面的输入和输出细节：
最开始，评分程序会写入N（图的点数）。然后你需要写入下面三种格式的内容：
R i j
U i j
Q
R U Q代表着字符'R'，'U'，'Q'，i和j在1到N之间。
第一种'R'意味着移除边(i,j)（如果存在）。
第二种'U'意味着添加之前被删除的边(i,j)。
第三种'Q'询问原图是否还连通。评分程序会返回0（不连通）或者1（连通）。
当你的程序准备输出原图，你应该单独输出一行，只包含一个'A'。然后是N行，每行包含N个字符。
第i行的第j个字符如果是1，代表着原图存在(i,j)这条边；否则是0，代表不存在。
如果你输出的图是不正确的，你获得0分。否则，你获得的分基于你'Q'的次数。
如果你输出的'Q'不超过900次，你可以获得100%的分数。
如果你输出的'Q'多于900次，不超过5000次（假设是x次），你可以获得20%+80%*(900/x)的分数。
如果你输出的'Q'多于5000次，你可以获得0%的分数。
下面是一个输入输出的例子（<表示评分程序的输出，>代表你的程序的输出）：
I/O | 删除边的集合
----------------------------------
< 4 |
> R 1 2 | {{1,2}}
> Q |
< 1 |
> U 1 2 | {}
> R 3 4 | {{3,4}}
> Q |
< 1 |
> R 4 1 | {{3,4}, {4,1}}
> Q |
< 0 |
> U 3 4 | {{4,1}}
> U 1 4 | {}
> R 1 2 | {{1,2}}
> R 2 3 | {{1,2}, {2,3}}
> Q |
< 0 |
> U 3 2 | {{1,2}}
> R 3 1 | {{1,2}, {3,1}}
> Q |
< 0 |
> U 1 2 | {{3,1}}
> Q |
< 1 |
> U 3 1 | {}
> R 1 4 | {{1,4}}
> Q |
< 0 |
> A |
> 0111 |
> 1010 |
> 1100 |
> 1000 |
时间限制: 2000ms空间限制: 128MB
来源: Usaco2011 Mar Gold