题目： http://acm.hdu.edu.cn/showproblem.php?pid=1704
题意：最多能找出多少条不通的路。。。。。题目没有说明不会有回路，因为如果有回路的话，回路里的对手都不能分出胜负。。。。而杭电的数据说明了不会有回路的。
传递闭包：用来求图中，任意两点是否可以通，思想类似Floyed，都是3重循环，Floyed：是否存在一个中间点，使得从起点——》中间点——》终点跟短，传递闭包：是否存在一个中间点，起点到终点本来不通的，但从起点——》中间点——》终点这条路走的话就通了（书上本来是g[i][j] = g[i][j] || (g[i][k] && g[k][j])的，但是输入图的时候g[i][j]本来就等于1了，所以后面代码只要更新不通的，而要更新的条件就是同时满足g[i]]k] == 1和g[k][j] == 1,所以可以看到下面的代码中的三重循环加了两个if语句,如果没有这两个if语句就会超时)）。。。。（都是松弛思想）
代码：
#include <iostream>
using
namespace
std;
const
int
M =
555
;
int
g[M][M];
int
main()
{
int
t;
scanf(
"
%d
"
, &
t);
while
(t--
)
{
memset(g,
0
,
sizeof
(g));
int
n, m;
scanf(
"
%d%d
"
, &n, &
m);
while
(m--
)
{
int
a, b;
scanf(
"
%d%d
"
, &a, &
b);
g[a][b]
=
1
;
}
for
(
int
k =
1
; k <= n; k++
)
{
for
(
int
i =
1
; i <= n; i++
)
{
if
(g[i][k])
{
for
(
int
j =
1
; j <= n; j++
)
{
if
(g[k][j])
{
g[i][j]
=
1
;
}
}
}
}
}
int
ans =
0
;
for
(
int
i =
1
; i <= n; i++
)
{
for
(
int
j = i +
1
; j <= n; j++
)
{
if
(g[i][j] ==
0
&& g[j][i] ==
0
)
{
ans
++
;
}
}
}
printf(
"
%d\n
"
, ans);
}
return
0
;
}
