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

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條評論
主站蜘蛛池模板: 午夜私人 | 天天综合在线观看 | 一级一片| 精品国产免费观看久久久 | 亚洲精品免费日日日夜夜夜夜 | 97人人插 | 黄色毛片免费观看 | 一二区| 国产一区二区免费在线 | 99在线精品日韩一区免费国产 | 天天草天天草 | 中国一级毛片录像 | 亚洲精品色| 国产精品九九视频 | 久久大香香蕉国产免费网vrr | 亚洲精品久久成人福利 | 色www国产阿娇| 99久久99热精品免费观看国产 | 久久综合噜噜激激的五月天 | 婷婷综合激情网 | 国产美女a做受大片在线观看 | 成人区在线观看免费视频 | 天天干天天插天天 | 欧美亚洲中日韩中文字幕在线 | 毛片免费看| 亚洲国产精品综合久久久 | 欧美三级a| 夜夜操综合 | 亚洲 欧美 精品 中文第三 | 一级特黄性色生活片一区二区 | 欧美男女啪啪 | 青青青青青青久久久免费观看 | 哪里有毛片 | 99视频在线看观免费 | 免费播放国产一级 | 日韩a级片视频 | 亚洲精品天堂自在久久77 | 最新国产精品好看的国产精品 | 91亚洲国产系列精品第56页 | 4hu影院永久在线播放 | 日本黄 色 成 年 人免费观看 |