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

            Better man

            改變性格 改變命運!

             

            zoj 1015(弦圖)

            至今不明白原理
            無向圖中,如果任意邊數大于3的環,至少存在一條邊連接環中不相鄰的某兩
            個點,則稱此圖為弦圖(Chordal Graph),所以說這里的算法就是
            第一步:給節點編號
            設已編號的節點集合為A,未編號的節點集合
             1 /*
             2 無向圖中,如果任意邊數大于3的環,至少存在一條邊連接環中不相鄰的某兩
             3 個點,則稱此圖為弦圖(Chordal Graph)
             4 */
             5 #include <iostream>
             6 using namespace std;
             7 int n,m;
             8 bool map[1001][1001];
             9 bool used[1001];
            10 int seta[1001];
            11 void number()
            12 {
            13       memset(used,0,sizeof(used));
            14       used[1]=1;
            15       seta[n]=1;
            16       for(int num=n-1;num>=1;--num)
            17       {
            18             int Max=0;
            19             int p=0;
            20             for(int i=1;i<=n;++i)
            21                   if(!used[i])
            22                   {
            23                         int sum=1;
            24                         for(int k=n;k>=num;--k)
            25                               if(map[i][seta[k]])
            26                                     sum++;
            27                         if(sum>Max)
            28                         {
            29                               Max=sum;
            30                               p=i;
            31                         }
            32                   }
            33             seta[num]=p;
            34             used[p]=1;
            35       }
            36 }
            37 bool check()
            38 {
            39       int setc[1001];
            40       for(int i=1;i<n;++i)
            41       {
            42             int x=seta[i];
            43             int k=0;
            44             for(int j=i+1;j<=n;++j)
            45             {
            46                   int y=seta[j];
            47                   if(map[x][y])
            48                         setc[k++]=y;
            49             }
            50             if(k>1)
            51             {
            52                   for(int j=1;j<k;j++)
            53                         if(!map[setc[0]][setc[j]])return 0;
            54             }
            55       }
            56       return true;
            57 }
            58 int main()
            59 {
            60       int a,b;
            61       while(scanf("%d%d",&n,&m)&&n)
            62       {
            63             memset(map,0,sizeof(map));
            64             for(int i=1;i<=m;++i)
            65             {
            66                   scanf("%d%d",&a,&b);
            67                   map[b][a]=map[a][b]=1;
            68             }
            69             //編號
            70             number();
            71             if(check())printf("Perfect\n\n");
            72             else printf("Imperfect\n\n");
            73       }
            74       return 0;
            75 }
            為B
            開始時A為空,B包含所有節點。
            for num=n-1 downto 0 do
            {
            在B中找節點x,使與x相鄰的在A集合中的節點數最多,將x編號為num,
            并從B移入A
            }
            第二步:檢查
            for num=0 to n-1 do
            {
            對編號為num的節點x,設所有編號大于num且與x相鄰的節點集合為C,
            在集合C中找出編號最小的節點y,如果集合C中存在不等于y的節點z,
            且y與z間沒有邊,則此圖不是弦圖,退出。
            }
            檢查完了,則此圖是弦圖。


            posted on 2009-02-04 16:21 SHFACM 閱讀(637) 評論(0)  編輯 收藏 引用 所屬分類: ACM

            導航

            統計

            常用鏈接

            留言簿(2)

            隨筆檔案

            文章分類

            文章檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久久久99精品成人片| 久久精品国产2020| 亚洲精品无码专区久久久| 中文字幕热久久久久久久| 午夜精品久久久久久99热| 久久影院综合精品| 色8激情欧美成人久久综合电| 国产69精品久久久久9999APGF | 久久精品国产一区| 久久国产成人亚洲精品影院| 亚洲精品无码久久久久久| 91精品国产高清久久久久久io| 国产精品亚洲综合久久| 久久久久噜噜噜亚洲熟女综合| 久久免费看黄a级毛片| 久久精品国产半推半就| 99久久免费国产精品特黄| 93精91精品国产综合久久香蕉 | 久久久久人妻精品一区三寸蜜桃| 伊人久久大香线蕉AV一区二区| 久久久久这里只有精品 | 精品伊人久久久| 国内精品久久久久久久久| 久久久精品人妻一区二区三区蜜桃| 人人狠狠综合久久亚洲高清| 精品亚洲综合久久中文字幕| 久久这里只有精品首页| 亚洲国产成人精品女人久久久| 久久99热只有频精品8| 91精品国产乱码久久久久久| 久久人人爽人人人人爽AV | 久久久久亚洲AV无码去区首| 国产亚洲美女精品久久久久狼| 久久精品国产亚洲AV无码麻豆| 亚洲欧美成人综合久久久| 一本久久免费视频| 精品国产日韩久久亚洲| 亚洲综合久久久| 亚洲AV无码一区东京热久久| 久久这里只有精品首页| 久久婷婷人人澡人人爽人人爱|