• <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個點,M個邊,每個邊有個標號,定義一條路徑和為所有這條路徑上邊的GCD,求從1到2所有路徑的LCM

            解法:
            BFS,狀態修正下,用{未節點,子路徑的GCD},這樣總狀態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 閱讀(253) 評論(0)  編輯 收藏 引用 所屬分類: searchgraph

            <2011年2月>
            303112345
            6789101112
            13141516171819
            20212223242526
            272812345
            6789101112

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            97精品伊人久久大香线蕉| 国产精久久一区二区三区| 欧美久久一级内射wwwwww.| 久久久久亚洲AV无码专区桃色| AA级片免费看视频久久| 亚洲AⅤ优女AV综合久久久| 久久精品中文闷骚内射| 久久综合伊人77777麻豆| 热re99久久6国产精品免费| 国产精品成人99久久久久 | 精品熟女少妇a∨免费久久| 精品久久一区二区三区| 亚洲七七久久精品中文国产| 久久伊人五月丁香狠狠色| 国产精品日韩欧美久久综合| 无码人妻少妇久久中文字幕蜜桃| 91久久成人免费| 精品国产乱码久久久久久郑州公司| 欧美激情精品久久久久久| 久久国产一区二区| 人妻少妇久久中文字幕| 久久人人爽人人爽人人片AV不| 国产叼嘿久久精品久久| 中文字幕久久欲求不满| 久久精品国产亚洲av麻豆小说| 国产精品亚洲综合久久| 久久综合色之久久综合| 久久久久久免费一区二区三区| 久久婷婷激情综合色综合俺也去| 伊人色综合九久久天天蜜桃| 久久性生大片免费观看性| 国内精品久久久久久中文字幕| 国产成人久久777777| 91久久精品无码一区二区毛片| 欧美综合天天夜夜久久| 国产亚洲欧美成人久久片| 国产精品久久久久久福利69堂| 国内精品久久久久影院一蜜桃| 久久w5ww成w人免费| 国产美女久久久| 国产69精品久久久久9999|