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

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條評論
主站蜘蛛池模板: 国产亚洲精品看片在线观看 | 爱爱网站免费 | 一区二区三区视频 | 欧美爱爱网 | 亚洲精品区一区二区三区四 | 日韩色在线 | 九九色综合 | 日欧毛片| www.天天射| 欧美成人亚洲国产精品 | 久热这里只有精品99国产6 | 久久国产自偷自免费一区100 | 国产目拍亚洲精品一区二区三区 | 九九视频只有精品六 | 一级特黄aaa大片大全 | 性生活视频网 | 亚洲国产一区二区三区综合片 | 天天操天天爱天天干 | 黄色在线观看www | 神马影院我不卡手机版 | 97视频免费在线观看 | 日日操天天 | 国产成人综合自拍 | 亚洲夂夂婷婷色拍ww47 | 国产91精品福利在线观看 | 豆国产97在线 | 中国 | 今天的恋爱未删减在线观看 | 国产成+人+综合+亚洲专 | 网站免费黄色 | 欧美性色欧美a在线观看 | 中文字幕视频不卡 | 久久久久久综合一区中文字幕 | 奇米影视777欧美在线观看 | 欧美亚洲国产一级毛片 | 亚洲精品美女久久777777 | 在线观看www. | 天天做夜夜爽 | 欧美视频一区二区三区在线观看 | 亚洲欧洲日本精品 | 精品国产品香蕉在线 | 日本在线视频毛片 |