• <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
            數(shù)據(jù)加載中……

            POJ 1570 Exchange Rates 并查集

            并查集加上分?jǐn)?shù)運算就可以了。
            兩種物品之間的兌換比率可以用分?jǐn)?shù)來表示,兩種物品之間是否存在聯(lián)系用并查集來表示。

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

            typedef 
            struct {
                
            int a, b;
            } frac ;

            #define MAX_ITEM 64

            char item[MAX_ITEM][32];
            int item_cnt;

            struct {
                frac f;
                
            int p;
            set[MAX_ITEM];

            int gcd(int a, int b)
            {
                
            int t;

                
            if (a > b) {
                    a 
            ^= b;
                    b 
            ^= a;
                    a 
            ^= b;
                }

                
            while (a) {
                    t 
            = a;
                    a 
            = b % a;
                    b 
            = t;
                }

                
            return b;
            }

            frac init(
            int a, int b)
            {
                frac r;
                
            int g = gcd(a, b);

                r.a 
            = a / g;
                r.b 
            = b / g;

                
            return r;
            }

            frac mul(frac a, frac b)
            {
                
            return init(a.a * b.a, a.b * b.b);
            }

            frac div(frac a, frac b)
            {
                
            return init(a.a * b.b, a.b * b.a);
            }

            int find(int i)
            {
                
            int p;

                
            if (set[i].p == i)
                    
            return i;

                p 
            = find(set[i].p);
                
            set[i].f = mul(set[set[i].p].f, set[i].f);
                
            set[i].p = p;

                
            return p;
            }

            int insert(char *s)
            {
                
            int i;

                
            for (i = 0; i < item_cnt; i++)
                    
            if (!strcmp(s, item[i]))
                        
            return i;
                strcpy(item[item_cnt], s);
                
            return item_cnt++;
            }

            int main()
            {
                
            char op[16], sa[32], sb[32];
                
            int a, b, ia, ib, i, p;
                frac f;

                
            for (i = 0; i < MAX_ITEM; i++) {
                    
            set[i].p = i;
                    
            set[i].f = init(11);
                }

                
            while (scanf("%s", op), op[0!= '.') {
                    
            if (op[0== '!') {
                        scanf(
            "%d%s%*s%d%s"&a, sa, &b, sb);
                        ia 
            = insert(sa);
                        ib 
            = insert(sb);
                        find(ia);
                        p 
            = set[ia].p;
                        
            set[p].p = ib;
                        
            set[p].f = div(init(b, a), set[ia].f);
                    } 
            else {
                        scanf(
            "%s%*s%s", sa, sb);
                        ia 
            = insert(sa);
                        ib 
            = insert(sb);
                        find(ia);
                        find(ib);
                        
            if (set[ia].p == set[ib].p) {
                            f 
            = div(set[ia].f, set[ib].f);
                            printf(
            "%d %s = %d %s\n", f.b, item[ia], f.a, item[ib]);
                        } 
            else 
                            printf(
            "? %s = ? %s\n", item[ia], item[ib]);
                    }
                }

                
            return 0;
            }


            posted on 2010-07-22 11:59 糯米 閱讀(384) 評論(0)  編輯 收藏 引用 所屬分類: POJ

            性高湖久久久久久久久| 成人国内精品久久久久影院| 久久久网中文字幕| 97久久国产露脸精品国产| 狠狠色丁香婷婷久久综合不卡| 久久精品国产免费| 久久只有这精品99| 嫩草影院久久国产精品| 少妇熟女久久综合网色欲| 久久精品国产亚洲av高清漫画 | 久久国产精品无码HDAV| 欧美777精品久久久久网| 欧美亚洲国产精品久久| 伊人久久大香线蕉影院95| 成人久久免费网站| 久久久久亚洲爆乳少妇无 | 久久99中文字幕久久| 亚洲AV伊人久久青青草原| 国产精品一区二区久久| 少妇人妻88久久中文字幕| 久久se这里只有精品| 精品国产91久久久久久久| 久久精品国产日本波多野结衣| 久久WWW免费人成—看片| 日本精品久久久中文字幕| 国产成人久久精品一区二区三区| 久久夜色精品国产噜噜亚洲a| 国产精品成人99久久久久| 久久无码人妻一区二区三区午夜| 亚洲国产天堂久久久久久| 久久99精品国产99久久6| 国产成人综合久久精品尤物| 九九久久自然熟的香蕉图片| 性欧美丰满熟妇XXXX性久久久| 久久人人添人人爽添人人片牛牛| 久久久久亚洲AV成人网人人软件| 久久国产亚洲精品麻豆| 伊人色综合久久| 久久成人精品| 久久影视国产亚洲| 久久婷婷五月综合成人D啪|