• <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

            一级做a爰片久久毛片16| 久久www免费人成看国产片| 伊人久久成人成综合网222| 久久久亚洲精品蜜桃臀| 精品久久久久久久久免费影院 | 精品熟女少妇AV免费久久| 999久久久免费国产精品播放| 色欲综合久久中文字幕网| 久久久噜噜噜久久熟女AA片| 欧美伊香蕉久久综合类网站| 99久久香蕉国产线看观香| 久久精品国产99久久无毒不卡| 久久www免费人成看国产片| 亚洲精品乱码久久久久久自慰| 亚洲国产精品久久久久网站| 日产精品久久久久久久| 热99re久久国超精品首页| 久久99精品久久久大学生| 国产精久久一区二区三区| 色婷婷综合久久久久中文 | 久久精品中文闷骚内射| 区亚洲欧美一级久久精品亚洲精品成人网久久久久 | 国产精品嫩草影院久久| 久久久久av无码免费网| 国产成人综合久久久久久| 久久久久久久精品妇女99| 免费一级做a爰片久久毛片潮| 久久精品人人做人人爽电影| 久久99国产综合精品| 中文精品久久久久人妻不卡| 亚洲欧美日韩久久精品| 久久精品视频91| 久久av免费天堂小草播放| 日本免费久久久久久久网站| 久久人人爽人人爽人人片av高请| 一本久久免费视频| 亚洲欧美另类日本久久国产真实乱对白| 久久激情亚洲精品无码?V| 国产Av激情久久无码天堂| 无码专区久久综合久中文字幕| 国产成人精品综合久久久|