亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

HDU 1704 Rank (傳遞閉包)

系統 1986 0

題目: 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
      
      
        ;

}
      
    

HDU 1704 Rank (傳遞閉包)


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

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

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 国产成人精品日本亚洲专一区 | 六月婷婷久香在线视频 | 亚洲经典在线中文字幕 | 亚洲欧美日本国产综合在线 | 欧美国产综合 | 久久综合久久综合久久综合 | 国产一区二区三区国产精品 | 国产成人一区二区三中文 | 国产成人18黄禁网站免费观看 | 午夜情趣视频 | 久久久久久岛国免费网站 | 97色在线观看免费视频 | 久久99精品久久久久久黑人 | 天天操狠狠操夜夜操 | 精品久久久久中文字幕日本 | 成人嫩草研究院网站进 | 欧美曰韩免费视频一区 | 免费一级毛片在线播放欧美 | 欧美成人亚洲高清在线观看 | 综合中文字幕 | 神马影院我不卡在线观看 | 四虎影视国产精品亚洲精品hd | 日韩一级特黄毛片在线看 | 久久天天躁日日躁狠狠躁 | 国产精品线在线精品 | 亚洲美女视频免费 | 亚洲综合精品一区 | 夜夜撸天天干 | 国产日产欧美 | 精品久久免费视频 | www.4虎影院| 久久免费播放视频 | 奇米第九色 | 精品国产一区二区三区香蕉沈先生 | v片视频| 久久免费视频8 | 亚洲国产片 | 日本一级毛片视频网站 | 中文视频 | 久久精品福利 | www.免费黄色 |