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

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條評論
主站蜘蛛池模板: 中文字幕美日韩在线高清 | 俄罗斯三级毛片 | 中文字幕国产欧美 | 中文字幕久久网 | 久久国产中文字幕 | 国产性色视频 | 一区二区精品视频 | 久久久久久久久久久9精品视频 | 国产热热 | 欧美国一级毛片片aa | 国产国产成人人免费影院 | 亚洲国产成人超福利久久精品 | 五月天色婷婷在线 | 亚洲欧美精品久久 | 亚洲精品久久久中文字 | 一级特黄a免费大片 | 国产91精品一区二区视色 | 毛片免费看看 | 亚洲欧美在线综合一区二区三区 | 天天操天天干天搞天天射 | 69国产成人综合久久精品91 | c看欧美激情毛片 | 亚洲国产一区二区a毛片日本 | 欧美一级在线 | 国产一区二区三区免费在线观看 | 亚洲国产欧美日韩一区二区三区 | 国产日产精品久久久久快鸭 | 又刺激又黄的一级毛片 | 俄罗斯毛片免费大全 | 国产一级爱c片免费播放 | 激情综合视频 | 人人干人人干 | 久久这里只有精品久久 | 日韩高清不卡在线 | 午夜操一操 | 羞羞视频在线免费 | 四虎影视国产在线观看精品 | 亚洲在线免费观看 | 精品精品国产高清a毛片牛牛 | 成人毛片免费视频 | 久久久久久网 |