• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            糯米

            TI DaVinci, gstreamer, ffmpeg
            隨筆 - 167, 文章 - 0, 評論 - 47, 引用 - 0
            數據加載中……

            POJ 2492 A Bug's Life 并查集

            思路:

            這題的背景是亮點,描述如下:
            Background 
            Professor Hopper is researching the sexual behavior of a rare species of bugs. He assumes that they feature two different genders and that they only interact with bugs of the opposite gender. In his experiment, individual bugs and their interactions were easy to identify, because numbers were printed on their backs.
            Problem 
            Given a list of bug interactions, decide whether the experiment supports his assumption of two genders with no homosexual bugs or if it contains some bug interactions that falsify it.

            Hopper 在研究某種稀有蟲子的性行為。他假設蟲子們有兩種不同的性別,而且它們只跟異性發生關系。
            在他的試驗里,每個蟲子和它的性行為都很容易辨認,因為它們的背后印著號碼。
            給出一些蟲子的性行為,確定是否有同性戀的蟲子能推翻這個假設。

            同性戀確實讓人無法接受,無論是人還是蟲子。。

            這題的解法不是亮點,就是普通的并查集,數據量非常龐大,需要路徑壓縮。

            #include <stdio.h>
            #include 
            <string.h>

            int N, T, set[2048], val[2048];

            inline 
            int find(int idx)
            {
                
            static int stk[2048], i;

                
            for (i = 0set[idx]; i++{
                    stk[i] 
            = idx;
                    idx 
            = set[idx];
                }

                
            for (i--; i >= 0; i--{
                    val[stk[i]] 
            ^= val[set[stk[i]]];
                    
            set[stk[i]] = idx;
                }


                
            return idx;
            }


            int main()
            {
                
            int i, j, a, b, t, m, r;

                scanf(
            "%d"&T);
                
            for (t = 1; t <= T; t++{
                    scanf(
            "%d%d"&N, &m);
                    memset(
            set0, (N + 1* 4);
                    memset(val, 
            0, (N + 1* 4);
                    r 
            = 0;
                    
            while (m--{
                        scanf(
            "%d%d"&a, &b);
                        i 
            = find(a);
                        j 
            = find(b);
                        
            if (i == j) 
                            r 
            |= val[a] == val[b];
                        
            else {
                            
            set[i] = b;
                            val[i] 
            = !val[a];
                        }

                    }

                    printf(
            "Scenario #%d:\n%s\n\n"
                            t,
                            r 
            ? "Suspicious bugs found!" : "No suspicious bugs found!"
                            );
                }


                
            return 0;
            }

            posted on 2010-04-17 20:57 糯米 閱讀(747) 評論(0)  編輯 收藏 引用 所屬分類: POJ

            久久亚洲精品视频| 93精91精品国产综合久久香蕉| 亚洲&#228;v永久无码精品天堂久久| 精品人妻伦九区久久AAA片69| 久久亚洲高清综合| 2021最新久久久视精品爱| 久久亚洲精品成人AV| 久久久久婷婷| 精品久久久久久国产潘金莲| 久久AⅤ人妻少妇嫩草影院| 中文字幕无码av激情不卡久久 | 久久久精品人妻一区二区三区四 | 无遮挡粉嫩小泬久久久久久久 | 精品久久久久久国产牛牛app| 香蕉99久久国产综合精品宅男自| 久久丫精品国产亚洲av不卡| 精品国产青草久久久久福利| 国产成人久久精品激情| 区久久AAA片69亚洲| 久久99亚洲综合精品首页| 久久中文骚妇内射| 久久久久久伊人高潮影院| 久久99国产精品久久99| 国产精品一区二区久久精品涩爱 | 伊人久久大香线焦AV综合影院| 四虎国产精品免费久久久| 亚洲国产精品久久久天堂| 三级三级久久三级久久| 欧美久久亚洲精品| 国产亚洲精午夜久久久久久| 久久久久中文字幕| 免费观看久久精彩视频| 国产V亚洲V天堂无码久久久| 99久久久精品免费观看国产| 久久丫精品国产亚洲av不卡| 久久香蕉国产线看观看精品yw| 亚洲AV日韩精品久久久久久久 | 久久综合狠狠综合久久激情 | 久久夜色精品国产亚洲| 亚洲国产精品久久久久| 99久久精品国产综合一区|