青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

pku 1182

 2009年7月12日 星期日

題目鏈接:PKU 1182 食物鏈
 
分類:并查集的拓展(經典)


題目分析與算法模型

        本題是一道經典的并查集的拓展,其中比較一般的解法是設立三個group,因為一共有三種動物。但其實有一種更加簡便的方法,具體如下,利用向量的思考模式將三個group合并成一個并查集,同時對每個節點保持其到根結點的相對類別偏移量,定義為:
0——同類;
1——食物;
2——天敵;
對于樹中的每一個節點(動物),記錄其與根節點的相對偏移量,即上面的0,1和2,這樣就可以根據相對平移量計算出其和根節點所代表的動物的關系,合并節點時,注意兩棵樹的根節點之間的相對偏移量,這里有幾個公式需要自己推導,都在代碼中了;

Code:

 1
#include<stdio.h>
 2#define max 50005
 3
 4int n,k,i,j,parent[max],kind[max],count,a,b,d;
 5
 6void init(int n)
 7{
 8    for(j=1;j<=n;j++)
 9    {
10        parent[j]=-1;
11        kind[j]=0;
12    }

13}

14int find(int x)
15{
16    int t=parent[x];
17    if(t<0)return x;
18    parent[x]=find(t);
19    kind[x]=(kind[x]+kind[t])%3;
20    return parent[x];
21}

22void Union(int x,int y,int d)
23{
24    if(x>n||y>n)count++;
25    else if(d==1)
26    {
27        int root1=find(x),root2=find(y);
28        if(root1==root2)
29        {
30            if(kind[x]!=kind[y])count++;
31        }

32        else
33        {
34            if(parent[root1]<parent[root2])   //root1為根
35            {
36                parent[root1]+=parent[root2];
37                parent[root2]=root1;
38                kind[root2]=(kind[x]-kind[y]+3)%3;       //需要自己推導
39            }

40            else                              //root2為根
41            {
42                parent[root2]+=parent[root1];
43                parent[root1]=root2;
44                kind[root1]=(kind[y]-kind[x]+3)%3;
45            }

46        }

47    }

48    else   //d=2
49    {
50        if(x==y)count++;
51        else
52        {
53            int root1=find(x),root2=find(y);
54            if(root1==root2)
55            {
56                if(kind[x]!=(kind[y]+1)%3)count++//需要自己推導
57            }

58            else
59            {
60                if(parent[root1]<parent[root2])   //root1為根
61                {
62                    parent[root1]+=parent[root2];
63                    parent[root2]=root1;
64                    kind[root2]=(kind[x]-kind[y]+5)%3;       //需要自己推導
65                }

66                else                              //root2為根
67                
68                    parent[root2]+=parent[root1];
69                    parent[root1]=root2;
70                    kind[root1]=(kind[y]-kind[x]+4)%3;      //需要自己推導
71                }

72            }

73        }

74    }

75}

76int main()
77{
78    scanf("%d%d",&n,&k);
79    init(n);
80    count=0;
81    for(i=0;i<k;i++)
82    {
83        scanf("%d%d%d",&d,&a,&b);
84        Union(a,b,d);
85    }

86    printf("%d\n",count);
87    return 0;
88}

89

posted on 2009-07-13 00:08 蝸牛也Coding 閱讀(1217) 評論(3)  編輯 收藏 引用

評論

# re: pku 1182[未登錄] 2009-12-17 12:12 YY

YTE   回復  更多評論   

# re: pku 1182 2010-02-12 16:04 Y

大家注意了,那個1代表根是這個節點的食物,別誤解了  回復  更多評論   

# re: pku 1182[未登錄] 2010-03-26 19:15 菜鳥

可以簡單說一下這幾條語句什么意思么?
kind[x]=(kind[x]+kind[t])%3;
kind[root2]=(kind[x]-kind[y]+3)%3;
kind[root2]=(kind[x]-kind[y]+5)%3;
  回復  更多評論   


只有注冊用戶登錄后才能發表評論。
網站導航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


<2009年7月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            欧美xxx在线观看| 亚洲无线一线二线三线区别av| 欧美中文日韩| 欧美一级电影久久| 久久国产欧美精品| 久久亚洲风情| 欧美激情精品久久久久久| 欧美精品综合| 国产精品美女久久久久av超清 | 亚洲免费观看高清完整版在线观看熊| 亚洲精品一区在线观看| 亚洲视频免费看| 久久精品视频在线观看| 欧美成人在线网站| 欧美视频在线免费看| 国产精品无码永久免费888| 韩国成人精品a∨在线观看| 亚洲精品国产精品国自产观看| 9久草视频在线视频精品| 欧美高清在线| 国产伦精品一区二区三区免费| 狠狠色丁香婷婷综合久久片| 日韩视频永久免费| 久久精品国语| 亚洲伦理久久| 久久久99精品免费观看不卡| 欧美日韩亚洲网| 国产曰批免费观看久久久| 亚洲毛片一区二区| 久久久亚洲高清| 亚洲午夜性刺激影院| 欧美成人性网| 黄色在线一区| 欧美在线在线| 一本色道久久综合亚洲精品小说| 久久久一本精品99久久精品66| 欧美日韩视频在线一区二区观看视频 | 国产婷婷一区二区| 中国成人黄色视屏| 免费成人av在线| 亚洲欧美影音先锋| 欧美婷婷久久| avtt综合网| 亚洲大胆在线| 午夜视频精品| 国产精品日本一区二区| 99在线热播精品免费| 免费高清在线一区| 久久久久国产精品www | 国产午夜亚洲精品不卡| 亚洲永久免费视频| 亚洲久色影视| 欧美精品在线观看一区二区| 91久久极品少妇xxxxⅹ软件| 久久亚洲精品一区二区| 香蕉视频成人在线观看| 国产伦精品一区二区三区| 午夜精品www| 亚洲欧美三级在线| 国产日韩一区二区三区在线播放| 亚洲欧美日韩成人高清在线一区| 亚洲精品在线观看免费| 欧美日本在线| 亚洲永久字幕| 亚洲综合精品自拍| 国产日韩精品入口| 久久精品官网| 久久亚洲精品一区| 亚洲精品欧美在线| 99re8这里有精品热视频免费| 欧美日在线观看| 久久福利影视| 欧美国产亚洲精品久久久8v| 久久九九热re6这里有精品 | 在线成人免费视频| 欧美激情性爽国产精品17p| 欧美激情成人在线| 亚洲在线黄色| 久久九九精品| 亚洲精品中文字幕有码专区| 99re6这里只有精品| 国产亚洲精品久久久久婷婷瑜伽| 蜜桃久久av一区| 欧美日韩天堂| 裸体歌舞表演一区二区| 欧美精品日韩| 久久精品盗摄| 欧美激情一区二区三级高清视频| 亚洲小说欧美另类社区| 久久国产精品亚洲va麻豆| 亚洲精品久久久久中文字幕欢迎你| 一本色道久久综合亚洲91| 国模吧视频一区| 亚洲精品欧美一区二区三区| 国产日韩1区| 亚洲黄色精品| 国产人成精品一区二区三| 欧美成人综合一区| 国产精品天美传媒入口| 免费日韩成人| 国产伦精品一区二区三区视频孕妇 | 中文精品视频| 久久久久久久久蜜桃| 中文日韩欧美| 蜜臀久久99精品久久久久久9 | 亚洲第一区在线| 亚洲视频1区2区| 亚洲精品一二三区| 久久精品国产精品亚洲精品| 亚洲视频久久| 欧美国产精品v| 老司机午夜免费精品视频| 欧美日韩综合网| 亚洲电影免费观看高清完整版在线 | a91a精品视频在线观看| 在线免费观看欧美| 欧美影院午夜播放| 亚洲免费在线精品一区| 欧美女激情福利| 欧美福利视频| 国内视频精品| 欧美一区二区三区视频| 亚洲欧美在线观看| 国产精品www色诱视频| 亚洲人人精品| 日韩视频欧美视频| 欧美寡妇偷汉性猛交| 亚洲春色另类小说| 欧美精品日韩www.p站| 葵司免费一区二区三区四区五区| 国产麻豆成人精品| 亚洲欧美日韩精品久久亚洲区| 亚洲精品一二三| 欧美xart系列在线观看| 亚洲成色www8888| 亚洲人体影院| 欧美久久婷婷综合色| 亚洲精品一区二区三区在线观看| 亚洲清纯自拍| 欧美顶级艳妇交换群宴| 91久久精品视频| 99国产精品99久久久久久粉嫩| 麻豆久久婷婷| 亚洲激情视频在线| 这里只有精品电影| 国产精品白丝jk黑袜喷水| 亚洲在线网站| 久久综合国产精品| 亚洲国产综合91精品麻豆| 欧美成人三级在线| av成人福利| 久久福利一区| 91久久久久久| 欧美日韩综合久久| 亚洲欧美日韩一区二区三区在线| 久久精品国产欧美激情| 一区二区三区无毛| 欧美国产亚洲精品久久久8v| 亚洲人成网站在线播| 亚洲一区3d动漫同人无遮挡| 国产精品在线看| 久久久久久国产精品mv| 亚洲电影av| 欧美一级日韩一级| 亚洲国产精品日韩| 国产精品r级在线| 欧美在线一区二区三区| 亚洲韩日在线| 久久精品噜噜噜成人av农村| 亚洲国产综合在线| 国产日韩欧美精品| 欧美好骚综合网| 午夜在线一区二区| 亚洲精品在线观| 老司机午夜精品视频在线观看| 99精品国产99久久久久久福利| 国产九区一区在线| 欧美日韩八区| 久久久久久亚洲精品杨幂换脸 | 亚洲尤物精选| 亚洲电影免费观看高清完整版在线 | 国产亚洲欧美日韩一区二区| 免费观看成人| 午夜在线观看免费一区| 亚洲三级观看| 欧美成人中文字幕| 久久aⅴ乱码一区二区三区| 亚洲精选视频免费看| 国产亚洲精品一区二555| 欧美激情一二三区| 久久另类ts人妖一区二区| 亚洲午夜一级| 欧美在线高清| 正在播放亚洲一区| 宅男在线国产精品| 在线播放亚洲一区| 国产一区再线| 国产久一道中文一区| 欧美日韩在线第一页| 欧美成人午夜激情|