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

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條評論
主站蜘蛛池模板: 国产成+人+亚洲+欧美综合 | 久久99国产精品免费观看 | 天天干天天插天天操 | 日本午夜www高清视频 | 大乳女做爰中文字幕 | 亚洲欧美综合久久 | 四虎永久免费地址ww417 | 中文精品久久久久中文 | xxxx性xx另类 | 久久精品国产免费 | 国产一区二区在免费观看 | 欧美日韩视频一区三区二区 | 香蕉成人 | 日本伊人色综合网 | 国产91在线 | 欧美 | 老妇女人一级毛片 | 2019天天干天天操 | 羞羞网站在线看 | 中文字幕一区二区三区有限公司 | 欧美一级特黄一片免费 | 日韩欧美视频 | a成人在线 | 亚洲精品一区二区三区香蕉在线看 | 日本一区二区三区免费高清在线 | 中文字幕日韩欧美一区二区三区 | 国产图片区 | 精品免费| 日韩精品久久久毛片一区二区 | 日韩高清在线日韩大片观看网址 | 天天se天天cao | 国产福利在线播放 | 国产黄色一级大片 | 不卡国产| 久热re这里只有精品视频 | 久国产精品久久精品国产四虎 | 精品国产福利在线 | 中文字幕或区 | 欧洲成人免费视频 | 国产激情视频一区二区三区 | a一级日本特黄aaa大片 | 天天曰天天干 |