題目: 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 ; }
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
