題目： http://acm.hdu.edu.cn/showproblem.php?pid=1704
?
題意：最多能找出多少條不通的路。。。。。題目沒有說明不會有回路，因為如果有回路的話，回路里的對手都不能分出勝負。。。。而杭電的數(shù)據(jù)說明了不會有回路的。
?
傳遞閉包：用來求圖中，任意兩點是否可以通，思想類似Floyed，都是3重循環(huán)，F(xiàn)loyed：是否存在一個中間點，使得從起點——》中間點——》終點跟短，傳遞閉包：是否存在一個中間點，起點到終點本來不通的，但從起點——》中間點——》終點這條路走的話就通了（書上本來是g[i][j] = g[i][j] || (g[i][k] && g[k][j])的，但是輸入圖的時候g[i][j]本來就等于1了，所以后面代碼只要更新不通的，而要更新的條件就是同時滿足g[i]]k] == 1和g[k][j] == 1,所以可以看到下面的代碼中的三重循環(huán)加了兩個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
;
}
更多文章、技術(shù)交流、商務合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
