HDU 5961 传递

/ 0评 / 0

Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
我们称一个有向图$G$是传递的,当且仅当对任意三个不同的顶点$a$,若$G$中有 一条边从$a$到$b$且有一条边从$b$到$c$ ,则$G$中同样有一条边从$a$到$c$。
我们称图$G$是一个竞赛图,当且仅当它是一个有向图且它的基图是完全图。换句话说,将完全图每条边定向将得到一个竞赛图。
下图展示的是一个有$4$个顶点的竞赛图。

现在,给你两个有向图$P=(V$,$E_p)$和$Q =(V,E_e)$,满足:
1.   $E_P$与$E_e$没有公共边;
2.  $ (V,E_p \bigcup E_e)$是一个竞赛图。
你的任务是:判定是否$P$,$Q$同时为传递的。

Input

包含至多$20$组测试数据。
第一行有一个正整数,表示数据的组数。
对于每组数据,第一行有一个正整数n。接下来n行,每行为连续的n个字符,每 个字符只可能是 -PQ中的一种。
$\bullet$如果第$i$行的第$j$个字符为 P,表示有向图P中有一条边从$i$到$j$;
$\bullet$如果第$i$行的第$j$个字符为 Q,表示有向图Q中有一条边从$i$到$j$;
$\bullet$否则表示两个图中均没有边从$i$到$j$。
保证$1<=n<=2016$,一个测试点中的多组数据中的$n$的和不超过$16000$。保证输入的图一定满足给出的限制条件。

Output

对每个数据,你需要输出一行。如果 P&Q都是传递的,那么请输出 T。否则, 请输出 N (均不包括引号)。

Sample Input

[enlighter lang="c++"]
4
4
-PPP
--PQ

---Q

4
-P-P
--PQ

P--Q

4
-PPP

--QQ

--Q-
4
-PPP

--PQ

--Q-
[/enlighter]

Sample Output

Hint

在下面的示意图中,左图为图为Q。


注:在样例2中,P不是传递的。在样例4中,Q不是传递的。

Source 2016年中国大学生程序设计竞赛(合肥)-重现赛(感谢安徽大学)

题解

给出两张点集相同但没有公共边的有向图$P,Q$,且$P,Q$满足二者边集的并集构成竞赛图,试判断$P,Q$是否同时为传递的。一个有向图不是传递的只要存在三个点$a,b,c$满足右$a->b,b->c$,但是没有边$a->c$,考虑到数据范围只有$10^3$的规模,可以考虑$O(n^3)$枚举,$O(1)$判断是否为传递的,用邻接表父子关系,用邻接矩阵存边,总复杂度 $O(n*E^2)

Update:看到卿学姐写了随机化 害怕QYQ占坑。。。
卿学姐的随机化

发表评论

电子邮件地址不会被公开。 必填项已用*标注