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

            pku 2132 Cow Math BFS

            題意:
            N個點(diǎn),M個邊,每個邊有個標(biāo)號,定義一條路徑和為所有這條路徑上邊的GCD,求從1到2所有路徑的LCM

            解法:
            BFS,狀態(tài)修正下,用{未節(jié)點(diǎn),子路徑的GCD},這樣總狀態(tài)50000,GCD的解法用歐幾里得,LCM=a*b/gcd(a,b),注意高精度,我偷懶用了java。。。

            代碼:
             1 import java.util.*;
             2 import java.math.*;
             3 public class Main {
             4 
             5     /**
             6      * @param args
             7      */
             8     static class pair
             9     {
            10         int a,b;
            11         pair(int aa,int bb)
            12         {
            13             a=aa;
            14             b=bb;
            15         }
            16     }
            17     static int gcd(int a,int b)
            18     {
            19         while(b!=0)
            20         {
            21             int t=a%b;
            22             a=b;
            23             b=t;
            24         }
            25         return a;
            26     }
            27     static BigInteger gcd(BigInteger a,BigInteger b)
            28     {
            29         while(!b.equals(BigInteger.ZERO))
            30         {
            31             BigInteger t=a.mod(b);
            32             a=b;
            33             b=t;
            34         }
            35         return a;
            36     }
            37     public static void main(String[] args) {
            38         Scanner in=new Scanner(System.in);
            39         int n=in.nextInt();
            40         int map[][]=new int[n][n];
            41         boolean used[][]=new boolean[26][2005];
            42         LinkedList<pair> q=new LinkedList<pair>();
            43         for(int i=0;i<n;i++)
            44             for(int j=0;j<n;j++)
            45                 map[i][j]=in.nextInt();
            46         BigInteger lcm=BigInteger.ONE;
            47         BigInteger tmp[]=new BigInteger[2005];
            48         tmp[1]=BigInteger.ONE;
            49         for(int i=2;i<tmp.length;i++)
            50             tmp[i]=tmp[i-1].add(BigInteger.ONE);
            51         for(int i=0;i<26;i++)
            52             Arrays.fill(used[i], false);
            53         for(int i=0;i<n;i++)
            54             if(map[0][i]!=0)
            55             {
            56                 used[i][map[0][i]]=used[0][map[0][i]]=true;
            57                 q.add(new pair(i,map[0][i]));
            58             }
            59         while(!q.isEmpty())
            60         {
            61             pair top=q.pollFirst();
            62             //System.out.println(top.a+" "+top.b);
            63             if(top.a==1)
            64             {
            65                 BigInteger t=tmp[top.b].multiply(lcm);
            66                 t=t.divide(gcd(lcm.add(BigInteger.ZERO),tmp[top.b].add(BigInteger.ZERO)));
            67                 lcm=t;
            68                 continue;
            69             }
            70             for(int i=0;i<n;i++)
            71                 if(map[top.a][i]!=0&&!used[i][gcd(top.b,map[top.a][i])])
            72                 {
            73                     used[i][gcd(top.b,map[top.a][i])]=true;
            74                     q.add(new pair(i,gcd(top.b,map[top.a][i])));
            75                 }
            76         }
            77         System.out.println(lcm);
            78 
            79     }
            80 
            81 }

            posted on 2011-03-13 02:23 yzhw 閱讀(255) 評論(0)  編輯 收藏 引用 所屬分類: searchgraph

            <2010年11月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            導(dǎo)航

            統(tǒng)計

            公告

            統(tǒng)計系統(tǒng)

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            国产精品美女久久久久久2018| 久久WWW免费人成一看片| 久久久久精品国产亚洲AV无码| 欧美性猛交xxxx免费看久久久 | 亚洲人成无码网站久久99热国产| 国产精品久久久久蜜芽| 久久精品亚洲精品国产色婷| 久久久久亚洲精品男人的天堂| 久久精品中文无码资源站| 天天爽天天狠久久久综合麻豆| 91精品国产综合久久香蕉| 精品久久久久久久久免费影院| 天堂久久天堂AV色综合| 亚洲天堂久久精品| 午夜精品久久久久久久无码| 91视频国产91久久久| 性欧美大战久久久久久久久 | 久久久久亚洲AV片无码下载蜜桃| 国产成人精品久久亚洲| 久久精品aⅴ无码中文字字幕不卡| 国产精品xxxx国产喷水亚洲国产精品无码久久一区 | 国产精品美女久久久| 无码国内精品久久人妻麻豆按摩| 国产精品久久国产精品99盘| 亚洲七七久久精品中文国产| 高清免费久久午夜精品| 亚洲精品无码专区久久久| 欧美麻豆久久久久久中文| 91精品国产91久久久久久蜜臀| 久久亚洲私人国产精品vA| 色综合久久久久久久久五月| 看全色黄大色大片免费久久久| 秋霞久久国产精品电影院| 91精品免费久久久久久久久| 久久亚洲精品成人AV| 性做久久久久久久| 精品国产99久久久久久麻豆| 伊人色综合九久久天天蜜桃| 久久精品国产亚洲Aⅴ香蕉 | 日本国产精品久久| 久久久亚洲精品蜜桃臀|