并查集专题

1、poj 2236 Wireless Network

暮秋已至,初春未央。这么些季节各位小伙伴是还是不是都认为自己又变酷了一丢丢,嗯~~那不是幻觉,因为又到了您一年一度该穿“秋裤”的时候呀。在此贴上一条严重警告:所有的“雨水儿”们,别忘了添衣保暖!!

  题意:一张图上分布着n台坏了的统计机,并领会它们的坐标。两台修好的微机如若距离<=d就可以联网,也可以因此任何修好的微处理器直接相连。给出操作“O
x”表示修好x,给出操作“S x y”,请您判断x和y在那时候有没有连接上。

再过去的一段时间里,我拜读了Windows编程界的大神CharlesPetzold的创作,他是一位世界顶尖的技巧作家,写过的书籍影响了一代又一代的程序员,有时候想,为啥美国能首先现身互连网的巨无霸公司?当然因素是体系的,但有一点不可以照旧不可以认,像CharlesPetzold那样的一批优质技能作家起到了有力的促进功效。

  思路:不难并查集。

读完了由他编著且久负出名的那本《编码:隐匿在微机软硬件背后的言语》一书之后,又在中国大学MOOC看完了清华的《总计机思维导论》课程,让自家萌发了尝试写一些科普类小说的想法。除此之外,也有一对私心,就是经过创作来打点和加固自己的知识,我将尽自己所能来写好该连串的稿子,尽量使其全部。这么些系列会在“小宇滴”公众号平台上展先导发,指出读每一篇小说时挑一个整块时间来阅读。由于才疏学浅,有不正确之处还望我们马上提出。话不多说,现在启幕啦。

5588葡京线路 15588葡京线路 2


 1 #include<iostream>
 2 #include<cstdio>
 3 #include<memory.h>
 4 #include<cmath>
 5 using namespace std;
 6 int n, d;
 7 const int maxn = 1200;
 8 int pre[maxn];
 9 struct node
10 {
11     int x;
12     int y;
13 }cpt[maxn];
14 int Find(int x)
15 {
16     int r = x;
17     while (r != pre[r])
18     {
19         r = pre[r];
20     }
21     int i = x, j;
22     while (pre[i] != r)
23     {
24         j = pre[i];
25         pre[i] = r;
26         i = j;
27     }
28     return r;
29 }
30 void Join(int x, int y)
31 {
32     int px = Find(x), py = Find(y);
33     if (px != py) pre[px] = py;
34 }
35 int main()
36 {
37     while (~scanf("%d%d", &n, &d))
38     {
39         for (int i = 1; i <= n; i++) scanf("%d%d", &cpt[i].x, &cpt[i].y);
40         memset(pre, 0, sizeof(pre));
41         char op[3];
42         while (~scanf("%s", op))
43         {
44             if (op[0] == 'O')
45             {
46                 int p;
47                 scanf("%d", &p);
48                 pre[p] = p;
49                 for (int i = 1; i <= n; i++)
50                 {
51                     if (i == p)continue;
52                     double dis = sqrt(1.0*(cpt[i].x - cpt[p].x)*(cpt[i].x - cpt[p].x) + (cpt[i].y - cpt[p].y)*(cpt[i].y - cpt[p].y));
53                     if (dis <= d&&pre[i]!=0)
54                     {
55                         Join(i, p);
56                     }
57                 }
58             }
59             else
60             {
61                 int p, q;
62                 scanf("%d%d", &p, &q);
63                 if (Find(p) != Find(q))printf("FAIL\n");
64                 else printf("SUCCESS\n");
65             }
66         }
67     }
68     return 0;
69 }

自身先抛出一个难点——什么是电脑?
如同已经听到一个动静在说:“这么不难的事,还用回答么,那不就是电脑呗。能打游戏,能听歌,能上网,能使用各个帮扶软件。”如若您是如此想的话,可以跟着往下读。

View Code

处理器,百度百科给出了这样的诠释——它是当代一种用于高速总括的电子总计机器,可以展开数值计算,又足以拓展逻辑总结,还有着存储回忆作用。没错,说的简练一些,它就是一台会活动统计的机器。请我们先先记住那些紧要词
电动总计”。接下来,带着那七个字,想象你坐在一台时光机上,把方今的光阴先按下暂停键,追本溯源,跟随我的笔触,来一场时空之旅吧……

2、poj 1611 The Suspects

                               时光机——启航

  题意:有一个该校,有N个学生,编号为0-N-1,现在0号学生感染了非典,凡是和0在一个社团的人就会感染,并且这一个人一旦还加入了其余协会,他所在的协会照样全体感染,求感染的人数。

                                    用齿轮造一台计算器

时间:1639年; 地点:法国 巴黎

那儿,回溯到300多年前的法国巴黎。
你在时光机的屏幕上,看到一位16岁的少年,在房间里思考着什么,脸上带着一丝愁容,少年自言自语到:“唉,我费力的爹爹,每日都这样忙,若是有怎么样机器能替代他工作该是多么好啊,哪怕只是一个怎么工具,能减轻他的担当也行呀”。时光机的人间适时的显得出了政工的背景简介:那位小男孩的爹爹是一位法国巴黎的税务官,每一天享有大量的税务收支要求他来计量,工作万分艰苦,他的子女,也就是那位少年,希望能减轻伯伯的工作量。

豆蔻年华心想:”为何代替人行走的马车已经有了,而代替人测算的仪器却从未呢?既然没有,那我就造它一个出去。”,
可说造一台代表人举办总计的仪器谈何简单。最终,少年退而求其次,希望造出来一个能协助人总结的工具就行,不见得精光代表人去总结。即便如此,在即时来说也只是停留在幻想阶段。但是少年天资聪颖,真的是一个名副其实的天资。他拜访了地点多少个名牌的手艺人,认真探讨了齿轮机构的传动等一些机械知识。

瞬间三年过去,到了1642年。当时的少年也已经19岁了,此时他正怀着激动的心绪向大千世界发布自己的发明——一台精巧的仪器。少年说到:“我们快看,那是何等有趣而厉害的物件,我今日来介绍一下那台仪器。它至关紧要有16个齿轮,分成上下两有的,每一有的都是8个齿轮,所以它最高能臆度8位的数字,每个齿轮都有十个齿,依次表示0~9。要拓展总结时,首先,需求把地点部分垂直竖起排成一排的齿轮先人工转动到相应数字的义务,然后仪器那边有一个把手。”少年用手指了指,示意大家向那个地点看,接着说道:“当你摇动把手的时候,上边一排的齿轮会自动转动,啮合着下边的一排齿轮也一同旋转,当上边对应的齿轮转到9的时候,传动机构就会让它的下一个齿轮自动多转动一个齿(表示进位),当你摇动把手,把第二排的齿轮转动到对应的加数时,其实结果也就曾经出来了。那就贯彻了加法总括”。

“帕斯卡”仪器俯视图

下面一位观众听完介绍后,发出怀疑:“能自动总括倒是不错,但是,依据你说的来看,它也只好总计加减,并不能总结乘除啊!”,站在台上的豆蔻年华也赫然发现到了那个题材。但好歹,对于一个十九岁的男女来说,能成立出来那样的仪器,已经是天赋异禀了。之后,那种仪器很快在法兰西的贵族圈流传开来,那位叫“布莱兹·帕斯卡”的豆蔻年华也随着被不少人所熟稔。没错,正如你所想,他即使给人类科学史上预留浓墨重彩一笔的尤其“帕斯卡”,后来的人生里,帕斯卡立异了水银气压计,发明了注射器,创造了水压机(那么些都和液压有关,以至于后人为了回看他,将压强单位称为“帕斯卡”,简称“帕”,记作“Pa”),甚至在有生之年患病的时候,他也从没扬弃研究,开创了或者是全人类的首先条公共小车线路——利用巴黎一辆有着众多座席的马车来载客。

“帕斯卡”加法器立体图

“帕斯卡”加法器开创了人类历史上首回用机器帮助人举办测算的开头,现今保留下去的大体有5台,例如在法国首都工艺校园和大英博物馆,都能收看它的“身影”,据传在中华紫禁城博物院,还有两台铜制的复制品,是当年别人送给慈禧太后皇太后的礼品,但皇太后何地知道它的微妙,只把它看做西洋的玩具摆放于深宫之中。

可那台仪器的老毛病也正如它的名字一样——只可以总计加减法。在帕斯卡逝世近十年之后,又一位
“科学巨匠”
创设了那台仪器的升官版,他的熏陶在整整现代科学史上,都是意思紧要且深刻的。那位“巨人”就是………

——————————————————未完待续——————————————————

  思路:并查集,合并的时候顺便总括人数。

5588葡京线路 35588葡京线路 4

 1 #include<iostream>
 2 using namespace std;
 3 const int maxn = 30010;
 4 int pre[maxn];
 5 int Cnt[maxn];
 6 int Find(int x)
 7 {
 8     int r = x;
 9     while (r != pre[r])
10     {
11         r = pre[r];
12     }
13     int i = x, j;
14     while (pre[i] != r)
15     {
16         j = pre[i];
17         pre[i] = r;
18         i = j;
19     }
20     return r;
21 }
22 void Join(int x, int y)
23 {
24     int fx = Find(x), fy = Find(y);
25     if (fx != fy) pre[fx] = fy,Cnt[fy]+=Cnt[fx];
26 }
27 int main()
28 {
29     int n, m;
30     while (~scanf("%d%d", &n, &m))
31     {
32         for (int i = 0; i <= n; i++) pre[i] = i,Cnt[i]=1;
33         if (n == 0 && m == 0)break;
34         for (int i = 0; i < m; i++)
35         {
36             int k;
37             scanf("%d", &k);
38             int pre, now;
39             for (int i = 0; i < k; i++)
40             {
41                 int x;
42                 scanf("%d", &x);
43                 if (i == 0) pre = now = x;
44                 else
45                 {
46                     now = x;
47                     Join(now, pre);
48                     pre = now;
49                 }
50             }
51         }
52         //int cnt = 0;
53         //for (int i = 0; i < n; i++)
54         //{
55         //    if (Find(i) == Find(0)) cnt++;
56         //}
57         printf("%d\n", Cnt[Find(0)]);
58     }
59     return 0;
60 }

View Code

3、hdu 1213 How Many Tables

  题意:多个人若相互认识,则坐在同一张桌子上。问须要有些张桌子。

  思路:并查集,合并的时候更新剩余连通块。

5588葡京线路 55588葡京线路 6

 1 #include<iostream>
 2 using namespace std;
 3 const int maxn = 1010;
 4 int pre[maxn];
 5 int cnt;
 6 int Find(int x)
 7 {
 8     int r = x;
 9     while (r != pre[r])
10     {
11         r = pre[r];
12     }
13     int i = x, j;
14     while (pre[i] != r)
15     {
16         j = pre[i];
17         pre[i] = r;
18         i = j;
19     }
20     return r;
21 }
22 void Join(int x, int y)
23 {
24     int fx = Find(x), fy = Find(y);
25     if (fx != fy) pre[fx] = fy, cnt--;
26 }
27 int main()
28 {
29     int t;
30     scanf("%d", &t);
31     while (t--)
32     {
33         int n, m;
34         scanf("%d%d", &n, &m);
35         cnt = n;
36         for (int i = 1; i <= n; i++) pre[i] = i;
37         for (int i = 0; i < m; i++)
38         {
39             int x, y;
40             scanf("%d%d", &x, &y);
41             Join(x, y);
42         }
43         printf("%d\n", cnt);
44     }
45     return 0;
46 }

View Code

4、hdu 3038 How Many Answers Are
Wrong

  题意:给你M个区间和,问你有多少个是与眼前争持的。

  思路:带权并查集,利用并查集形成集合树,利用sum数组记录集合树中当前节点i到根之间的边的权值和,若是当前四个节点不在同一棵集合树中,那么通过多个聚众树合并,调整权值,使可以有限支撑合法的,所以只须要联合,将一棵树的根变为另一棵树的根的子节点,然后建边,因为f[i]<i,i<j,f[j]<j,所以s=sum[j]+sum[f[j]]-sum[i]因为眼下j的根是f[j],所以要增加新加的边权,那么新的边权既能够经过那个方程求取即可。

5588葡京线路 75588葡京线路 8

 1 //利用并查集形成集合树,利用sum数组记录集合树中当前节点i到根之间的边的权值和,如果当前两个节点不在同一棵集合树中,那么通过两个集合树合并,调整权值,使能够保证合法的,所以只需要合并,将一棵树的根变为另一棵树的根的子节点,然后建边,因为f[i]<i,i<j,f[j]<j,所以s=sum[j]+sum[f[j]]-sum[i]因为当前j的根是f[j],所以要加上新加的边权,那么新的边权既可以通过这个方程求取即可
 2 #include<stdio.h>
 3 #define MAXN 200010
 4 int f[MAXN], r[MAXN];
 5 int find(int x)
 6 {
 7     if (x == f[x])
 8         return f[x];
 9     int t = find(f[x]);
10     r[x] = r[x] + r[f[x]];//这里首先要对这个递归的过程很了解,当递归到某一层时,x还未接到根节点上,所以r[x]表示的是x到f[x]的距离,经上一步操作,f[x]已经接到根节点上了,所以r[f[x]]表示的是父节点到根节点的距离所以x到根节点的距离就直接等于r[x]+r[f[x]]
11     f[x] = t;
12     return f[x];
13 }
14 int fun(int x, int y)
15 {
16     if (x>y)
17         return x - y;
18     else y - x;
19 }
20 int Union(int x, int y, int sum)
21 {//传进来时x<y
22     int a = find(x);
23     int b = find(y);
24     if (a == b)
25     {
26         if (fun(r[x], r[y]) == sum)
27             return 0;
28         else return 1;
29     }
30     else
31     {
32         f[a] = b;
33         r[a] = r[y] + sum - r[x];//r[y]表示y到b的距离,r[x]表示x到a的距离,sum表示x到y的距离,现在要将a接到b后面,那么r[a]很表示a到b的距离,很明显就是这个式子了   
34         return 0;
35     }
36 }
37 int main()
38 {
39     int n, m, i, ans, a, b, s;
40     while (scanf("%d %d", &n, &m) != EOF)
41     {
42         ans = 0;
43         for (i = 0; i <= n; i++)
44         {
45             f[i] = i;
46             r[i] = 0;
47         }
48         for (i = 1; i <= m; i++)
49         {
50             scanf("%d %d %d", &a, &b, &s);
51             a--;//左区间减一,方便处理
52             if (Union(a, b, s))
53                 ans++;
54         }
55         printf("%d\n", ans);
56     }
57     return 0;
58 }

View Code

5、poj 1182 食物链

  题意:有  3  种动物,相互吃与被吃,现在报告您  m  句话,其中有真有假,叫你判定假的个数  (  即使面前没有与眼前话冲突的,即认为其为心声  )。每句话开端都有三个数 D A B,当D = 1时,表示A 和B是同类,当D = 2时表示A 吃 B。

  思路:带权并查集。

5588葡京线路 95588葡京线路 10

 1 #include<iostream>
 2 using namespace std;
 3 const int maxn = 50010;
 4 int n,k;
 5 int pre[maxn], r[maxn];
 6 //根据“x与p[x]能否确定两者之间的关系”来划分,若能确定x与p[x]的关系,则它们同属一个集合。
 7 //p[x]表示x的根结点。r[x]表示p[x]与x的关系。r[x] == 0 表示p[x]与x同类;1表示p[x]吃x;2表示x吃p[x]。
 8 void Init()
 9 {
10     for (int i = 0; i <= n; i++)
11     {
12         pre[i] = i;
13         r[i] = 0;
14     }
15 }
16 
17 //每次通过儿子对父亲的关系,父亲对爷爷的关系,得到儿子对爷爷的关系
18 int Find(int x)
19 {
20     if (pre[x] == x) return x;
21     else
22     {
23         int fa = pre[x];
24         pre[x] = Find(fa);
25         r[x] = (r[x] + r[fa]) % 3;
26         return pre[x];
27     }
28 }
29 
30 bool Union(int x, int y, int d)
31 {//d=1:x和y是同类;d=2,x吃y
32     int rx = Find(x), ry = Find(y);
33     if (rx == ry)return true;
34     else
35     {
36         pre[ry] = rx;
37         r[ry] = (r[x] - r[y] + 2 + d) % 3;
38         //r[ry]=(3-r[y]+(d-1)+r[x])%3(可推)
39         return false;
40     }
41 }
42 
43 int main()
44 {
45     scanf("%d%d", &n, &k);
46     Init();
47     int cnt = 0;
48     while (k--)
49     {
50         int d, x, y;
51         scanf("%d%d%d", &d, &x, &y);
52         if (x > n || y > n) cnt++;
53         else
54         {
55             bool same = Union(x, y, d);
56             if (same)
57             {
58                 if (d == 1)
59                 {
60                     //D == 1 表示X与Y为同类,而从r[X] != r[Y]可以推出 X 与 Y 不同类。矛盾。
61                     if (r[x] != r[y])
62                     {
63                         cnt++;
64                     }
65                 }
66                 else
67                 {
68                     if ((r[y] + 3 - r[x]) % 3 != 1)
69                     {//(X 与Y为同类)或者 r[X] == ( r[Y] + 1 ) % 3 (Y吃X )则此话为假。
70                         cnt++;
71                     }
72                 }
73             }
74         }
75     }
76     printf("%d\n", cnt);
77     return 0;
78 }

View Code

6、poj 1417 True Liars(并查集+DP)

  题意:给出p1+p2个人,其中p1个是好人,p2个是坏人。然后有部分事关
,a说b是老实人(坏人).其中没有顶牛的,判断是或不是有唯一解判断哪些人是老实人,哪些人是坏人。其中相比较关键的是,好人总说真话,坏人总说假话。

  思路:

  ①一个人说另一个人是老实人,那么只要此人是好人,表达对方的确是老实人,若是那个是禽兽,表达那句话是假的,对方也是坏人。

  ②即使一个人说另一个人是坏人,那么一旦此人是老实人,表达对方是禽兽,若是那几个是坏人,表达对方是好人。

也就是假诺条件是yes表达那七个是如出一辙集合的,否则是多少个不等的集结。用r[i]代表i结点与根结点的关联,0为同样集合,1为分裂集合。

经过并查集,可以将所有人分为若干个会聚,其中对于每一个凑合,又分为四个聚众(好人和歹徒,可是不掌握怎样是老实人,哪些是禽兽,我们唯有相对关系)

用dp[i][j]表示前i个汇聚中好人为j的种数,即使dp[cnt][p1]!=1表达方案不唯一,或者无解。belong[i][0]表示i属于哪个大类,belong[i][1]代表i属于该大类的哪一个小类,choose[i]倒推找出接纳的大集合i的两类中是哪类,然后升序输出好人的号子。

5588葡京线路 115588葡京线路 12

  1 #include<iostream>
  2 using namespace std;
  3 int n, p1, p2;
  4 const int maxn = 1100;
  5 int pre[maxn];//i的父亲
  6 int r[maxn];//i和pre[i]的关系
  7 //0:同类;1:不同类
  8 
  9 bool vis[maxn];
 10 
 11 int cntnum[maxn][2];//cntnum[i][j]表示把第i个集合分成两个部分的人数
 12 
 13 int dp[maxn][310];//dp[i][j]表示前i个集合中好人为j的种数
 14 
 15 int belong[maxn][2];//belong[i][0]表示i属于哪个大类,belong[i][1]表示i属于该大类的哪一个小类(对应cntnum)
 16 int id[maxn];
 17 //根据孩子与父亲,父亲与祖父之间的关系可以推出孩子与祖父的关系
 18 int Find(int x)
 19 {
 20     if (pre[x] == x) return x;
 21     else
 22     {
 23         int fa = pre[x];
 24         pre[x] = Find(fa);
 25         r[x] = r[x] ^ r[fa];
 26         return pre[x];
 27     }
 28 }
 29 
 30 void Union(int x, int y, int k)
 31 {
 32     int rx = Find(x), ry = Find(y);
 33     if (rx != ry)
 34     {
 35         pre[rx] = ry;
 36         r[rx] = (r[x] - r[y] + 2 + k) % 2;
 37     }
 38 }
 39 
 40 void Init()
 41 {
 42     for (int i = 0; i <= p1 + p2; i++)
 43     {
 44         pre[i] = i;
 45         r[i] = 0;
 46     }
 47 }
 48 int main()
 49 {
 50     while (~scanf("%d%d%d", &n, &p1, &p2))
 51     {
 52         if (n == 0 && p1 == 0 && p2 == 0) break;
 53         Init();
 54         char s[5];
 55         int a, b, k;
 56         for (int i = 0; i < n; i++)
 57         {
 58             scanf("%d%d%s", &a, &b, s);
 59             if (s[0] == 'y') k = 0;
 60             else k = 1;
 61             Union(a, b, k);
 62         }
 63         //处理完后,得到若干个集合,每个集合中两两同类或不同类
 64         //2:找到有多少个大集合,每个大集合中同类及不同类的个数
 65         memset(vis, 0, sizeof(vis));
 66         memset(cntnum, 0, sizeof(cntnum));
 67         memset(belong, 0, sizeof(belong));
 68 
 69         int cnt = 0;
 70         for (int i = 1; i <= p1 + p2; i++)
 71         {
 72             if (!vis[i])
 73             {
 74                 cnt++;
 75                 int f = Find(i);
 76                 id[f] = cnt;//对每个大集合的根进行分类
 77                 for (int j = i; j <= p1 + p2; j++)
 78                 {
 79                     if (Find(j) == f)
 80                     {
 81                         vis[j] = true;
 82                         cntnum[cnt][r[j]]++;
 83                         belong[j][0] = cnt;
 84                         belong[j][1] = r[j];
 85                     }
 86                 }
 87             }
 88         }
 89         //DP
 90         memset(dp, 0, sizeof(dp));
 91         dp[0][0] = 1;
 92         for (int i = 1; i <= cnt; i++)
 93         {
 94             for (int j = p1; j >= 0; j--)
 95             {
 96                 if (j - cntnum[i][0] >= 0 && dp[i - 1][j - cntnum[i][0]] > 0)
 97                 {
 98                     dp[i][j] += dp[i - 1][j - cntnum[i][0]];
 99                 }
100                 if (j - cntnum[i][1] >= 0 && dp[i - 1][j - cntnum[i][1]] > 0)
101                 {
102                     dp[i][j] += dp[i - 1][j - cntnum[i][1]];
103                 }
104             }
105         }
106 
107         //输出
108         if (dp[cnt][p1] != 1) printf("no\n");
109         else
110         {
111             int choose[maxn];//倒推找出选择的大集合的两类中是哪一类
112             int totalpeople = p1;
113             for (int i = cnt; i >= 1; --i)
114             {
115                 if (dp[i][totalpeople] == dp[i - 1][totalpeople - cntnum[i][0]])
116                 {
117                     choose[i] = 0;
118                     totalpeople -= cntnum[i][0];
119                 }
120                 else if (dp[i][totalpeople] == dp[i - 1][totalpeople - cntnum[i][1]])
121                 {
122                     choose[i] = 1;
123                     totalpeople -= cntnum[i][1];
124                 }
125             }
126 
127             for (int i = 1; i <= p1 + p2; i++)
128             {
129                 int fa = Find(i);
130                 int set_id = id[fa];
131                 if (belong[i][0] == set_id&&belong[i][1] == choose[set_id])
132                 {
133                     printf("%d\n", i);
134                 }
135             }
136             printf("end\n");
137         }
138     }
139     return 0;
140 }

View Code

7、poj 1456 Supermarket

  题意:有N件商品,分别交由商品的市值和销售的末尾期限,只要在最今天期以前销售处,就能得到相应的盈利,并且销售该商品必要1天时间。问销售的最大利润。

  思路:先把富有成品依据利润从大到小排序,如若一个成品a占用了一个日子后,那么一旦下次又有一个出品b和成品a的甘休日期是一模一样的,不过万分日期以被挤占了,所以就要往前挪动1天,那么就可以用并查集进行标记,在a占用了很是日期后,把a的利落日期指向前一个日子,那样的话,可以一贯搜索到她要并吞到哪一个时日。

5588葡京线路 135588葡京线路 14

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 int n;
 5 const int maxn = 10010;
 6 const int maxt = 10010;
 7 struct node
 8 {
 9     int pi;
10     int di;
11 }goods[maxn];
12 
13 int pre[maxt];
14 int Find(int x)
15 {
16     int r = x;
17     while (r != pre[r])
18     {
19         r = pre[r];
20     }
21     int i = x, j;
22     while (pre[i] != r)
23     {
24         j = pre[i];
25         pre[i] = r;
26         i = j;
27     }
28     return r;
29 }
30 
31 void Union(int x, int y)
32 {
33     int fx = Find(x), fy = Find(y);
34     if (fx != fy)
35     {
36         if (fx < fy) pre[fy] = fx;
37         else pre[fx] = fy;
38     }
39 }
40 
41 
42 void Init()
43 {
44     for (int i = 0; i <maxt; i++)
45     {
46         pre[i] = i;
47     }
48 }
49 bool Cmp(const node&a, const node&b)
50 {
51     if (a.pi == b.pi)return a.di > b.di;
52     else return a.pi > b.pi;
53 }
54 int main()
55 {
56     while (~scanf("%d", &n))
57     {
58         Init();
59         for (int i = 0; i < n; i++)
60         {
61             scanf("%d%d", &goods[i].pi, &goods[i].di);
62         }
63         sort(goods, goods + n, Cmp);
64 
65         int sum = 0;
66         
67         for (int i = 0; i < n; i++)
68         {
69             int tt = goods[i].di;
70             int ff = Find(tt);
71             if (ff > 0)
72             {
73                 Union(ff, ff - 1);
74                 sum += goods[i].pi;
75             }
76         }
77         printf("%d\n", sum);
78     }
79     return 0;
80 }

View Code

8、poj 1703 Parity game

  题意:有一个长短已知的01串,给出[l,r]本条距离中的1是奇数个仍然偶数个,给出一一日千里语句问前多少个是毋庸置疑的。

  思路:将[l,r]其一距离变成(l-1,r],那么1的个数就足以象征为sum[r]-sum[l-1],也就确定了奇偶性,大家可以用r[]数组表示那几个端点到它的根节点的1的奇偶(那几个间隔就是(i,root(i)](0代表偶,1象征奇)
 对于每个输入的距离,我们摸索它们的根节点是还是不是同样。

         
①万一相同,阐明那几个间隔的奇偶性在前头早已查出,那么直接判断即可

         
②比方差异,那么就是u-1与v此时不在同一个集结中,则统一时更新r[].

5588葡京线路 155588葡京线路 16

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 int n, m;
 5 const int maxn = 5050;
 6 int pre[maxn];
 7 int val[maxn];
 8 struct node
 9 {
10     int ll;
11     int rr;
12     int d;
13 }qry[maxn];
14 int Map[maxn * 2];
15 int Find(int x)
16 {
17     if (x == pre[x]) return x;
18     else
19     {
20         int fa = pre[x];
21         pre[x] = Find(fa);
22         val[x] = (val[x] + val[fa]) % 2;
23         return pre[x];
24     }
25 }
26 bool Union(int x, int y, int v)
27 {//x<y
28     int rx = Find(x), ry = Find(y);
29     if (rx == ry) return true;
30     else
31     {
32         if (rx < ry)
33         {
34             pre[ry] = rx;
35             val[ry] = (val[x] + v - val[y] + 2) % 2;
36         }
37         else
38         {
39             pre[rx] = ry;
40             val[rx] = (val[y] - v - val[x] + 2) % 2;
41         }
42         return false;
43     }
44 }
45 int main()
46 {
47     while (~scanf("%d", &n))
48     {
49         scanf("%d", &m);
50         int l, r, v;
51         char s[6];
52         int cnt = 0;
53         for (int i = 0; i < m; i++)
54         {
55             scanf("%d%d%s", &l, &r, s);
56             l = l - 1;
57             if (s[0] == 'e') v = 0;
58             else v = 1;
59             qry[i].ll = l, qry[i].rr = r, qry[i].d = v;
60             Map[cnt++] = l;
61             Map[cnt++] = r;
62         }
63         //离散化
64         sort(Map, Map + cnt);
65         cnt = unique(Map, Map + cnt) - Map;
66         for (int i = 0; i <= cnt; i++)
67         {
68             pre[i] = i;
69             val[i] = 0;
70         }
71         int ans = 0;
72         for (int i = 0; i < m; i++)
73         {
74             l = lower_bound(Map, Map + cnt, qry[i].ll) - Map;
75             r = lower_bound(Map, Map + cnt, qry[i].rr) - Map;
76             v = qry[i].d;
77             if (Union(l, r, v))
78             {
79                 if ((val[r] - val[l] + 2) % 2 != v)
80                 {
81                     break;
82                 }
83 
84             }
85             ans++;
86         }
87         printf("%d\n", ans);
88     }
89     return 0;
90 }

View Code

9、poj 1984 Navigation Nightmare

  题意:图上有一些村庄,村庄之间用只好指向北南西南的矛头的征程连接,村庄只好放在道路的双方。询问停止到第I个已知条件时某多个村子之间的曼哈顿距离。

  思路:先根据道路设出每个点的坐标,然后一旦某个已知条件已知,则统一。询问时判断四个山村是不是在同一个连通块即可。

5588葡京线路 175588葡京线路 18

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<vector>
  4 using namespace std;
  5 int n, m,k;
  6 const int maxn = 40050;
  7 const int maxm = 40050;
  8 const int maxk = 10050;
  9 struct qry
 10 {
 11     int t;
 12     int f1;
 13     int f2;
 14     int id;
 15 }qrys[maxk];
 16 int ans[maxk];
 17 
 18 struct stp
 19 {
 20     int f1;
 21     int f2;
 22     stp(int ff1 = 0, int ff2 = 0) :f1(ff1), f2(ff2)
 23     {
 24     }
 25 };
 26 vector<stp>stps;
 27 struct pt
 28 {
 29     int x;
 30     int y;
 31 }points[maxn];
 32 bool Cmp1(const qry&a, const qry&b)
 33 {
 34     return a.t < b.t;
 35 }
 36 
 37 int pre[maxn];
 38 int Find(int x)
 39 {
 40     if (pre[x] == x) return x;
 41     else
 42     {
 43         int fa = pre[x];
 44         pre[x] = Find(fa);
 45         return pre[x];
 46     }
 47 }
 48 bool Union(int x, int y)
 49 {
 50     int fx = Find(x), fy = Find(y);
 51     if (fx == fy) return true;
 52     else
 53     {
 54         pre[fx] = fy;
 55         return false;
 56     }
 57 }
 58 struct node
 59 {
 60     int to;
 61     char dir;
 62     int len;
 63     node(int tt=0,char c=0,int ll=0):to(tt),dir(c),len(ll){ }
 64 };
 65 vector<node>mp[maxn];
 66 bool vis[maxn];
 67 void DFS(int r)
 68 {
 69 
 70     int sz = mp[r].size();
 71     for (int i = 0; i < sz; i++)
 72     {
 73         int tx = points[r].x, ty = points[r].y;
 74         int v = mp[r][i].to, length = mp[r][i].len;
 75         if (vis[v])continue;
 76         switch (mp[r][i].dir)
 77         {
 78         case 'N':tx -= length;
 79             break;
 80         case 'E': ty += length;
 81             break;
 82         case 'S':tx += length;
 83             break;
 84         case 'W':ty -= length;
 85             break;
 86         }
 87         points[v].x = tx, points[v].y = ty;
 88         vis[v] = true;
 89         DFS(v);
 90     }
 91 }
 92 
 93 int main()
 94 {
 95     while (~scanf("%d%d", &n, &m))
 96     {
 97         for (int i = 0; i <= n; i++) mp[i].clear();
 98         stps.clear();
 99         for (int i = 1; i <= m; i++)
100         {
101             int u, v, l;
102             char op[10];
103             scanf("%d%d%d%s", &u, &v, &l,op);
104             mp[u].push_back(node(v, op[0], l));
105             char nc;
106             switch (op[0])
107             {
108             case 'N':
109                 nc = 'S';
110                 break;
111             case 'S':
112                 nc = 'N';
113                 break;
114             case 'E':
115                 nc = 'W';
116                 break;
117             case 'W':
118                 nc = 'E';
119                 break;
120             }
121             mp[v].push_back(node(u, nc, l));
122             stps.push_back(stp(u, v));
123         }
124         memset(vis, 0, sizeof(vis));
125         for (int i = 0; i <= n; i++)
126         {
127             if (mp[i].size())
128             {
129                 points[i].x = 0, points[i].y = 0;
130                 vis[i] = true;
131                 DFS(i);
132                 break;
133             }
134         }
135         scanf("%d", &k);
136         for (int i = 0; i < k; i++)
137         {
138             scanf("%d%d%d",&qrys[i].f1, &qrys[i].f2, &qrys[i].t);
139             qrys[i].id = i + 1;
140         }
141         sort(qrys, qrys + k, Cmp1);
142 
143         for (int i = 0; i <= n; i++) pre[i] = i;
144         int nowstep = 0;
145         for (int i = 0; i < k; i++)
146         {
147             int t = qrys[i].t;
148             for (; nowstep < t; nowstep++)
149             {
150                 int f1 = stps[nowstep].f1;
151                 int f2 = stps[nowstep].f2;
152                 Union(f1, f2);
153             }
154             int x = qrys[i].f1, y = qrys[i].f2;
155             int fx = Find(x), fy = Find(y);
156             if (fx != fy)
157             {
158                 ans[qrys[i].id] = -1;
159             }
160             else ans[qrys[i].id] = abs(points[x].x - points[y].x) + abs(points[x].y - points[y].y);
161         }
162         for (int i = 1; i <= k; i++)
163         {
164             printf("%d\n", ans[i]);
165         }
166     }
167     return 0;
168 }

View Code

10、hdu 1829 A Bug’s Life

  题意:给定一多级数对,例如a和b,表示a和b不是均等种性别,然后不断的付出那样的数对,问有没有争论的景况。

  思路:带权并查集。

5588葡京线路 195588葡京线路 20

 1 #include<iostream>
 2 using namespace std;
 3 const int maxn = 2100;
 4 int pre[maxn];
 5 int r[maxn];
 6 int n, m;
 7 void Init()
 8 {
 9     for (int i = 0; i <= n; i++)
10     {
11         pre[i] = i;
12         r[i] = 0;
13     }
14 }
15 int Find(int x)
16 {
17     if (pre[x] == x)return x;
18     else
19     {
20         int fa = pre[x];
21         pre[x] = Find(fa);
22         r[x] = r[x] ^ r[fa];
23         return pre[x];
24     }
25 }
26 
27 bool Join(int x, int y)
28 {
29     int fx = Find(x), fy = Find(y);
30     if (fx == fy)return true;
31     else
32     {
33         pre[fx] = fy;
34         r[fx] = r[x] ^ r[y] ^ 1;
35         return false;
36     }
37 }
38 int main()
39 {
40     int t;
41     int Case = 1;
42     scanf("%d", &t);
43     while (t--)
44     {
45         scanf("%d%d", &n, &m);
46         Init();
47         bool flag = true;
48         while (m--)
49         {
50             int u, v;
51             scanf("%d%d", &u, &v);
52             if (!flag)continue;
53             if (Join(u, v))
54             {
55                 if (r[u] ^ r[v] != 1)
56                 {
57                     flag = false;
58                 }
59             }
60         }
61         if (flag) printf("Scenario #%d:\nNo suspicious bugs found!\n\n", Case++);
62         else printf("Scenario #%d:\nSuspicious bugs found!\n\n", Case++);
63     }
64     return 0;
65 }

View Code

11、poj 2912 Rochambeau

  题意:有N个人玩剪刀石头布,其中有个人是评判,其余人分为3组。
那3组中每个组分别出剪刀,石头和布。 评判可以无限制出3个中的一个。
现在有M个回合,每个回合从N个人中自由选出四个人来玩,并交给结果。
须要输出最早找出评判的回合数,以及评判的数码。还有可能或不能够确定。

  思路:利用并查集建立起相对关系,枚举评判是哪一个,对有他参与的回合不予处理,如果在她不出席的回合中冒出了冲突,那么这厮必然就不是评判。

5588葡京线路 215588葡京线路 22

 1 #include<iostream>
 2 using namespace std;
 3 const int maxn = 510;
 4 const int maxm = 2010;
 5 int n, m;
 6 int pre[maxn];
 7 int r[maxn];//0:平局;1:pre[x]赢了x;2:x赢了pre[x]
 8 void Init()
 9 {
10     for (int i = 0; i <= n; i++)
11     {
12         pre[i] = i;
13         r[i] = 0;
14     }
15 }
16 struct stp
17 {
18     int u;
19     int v;
20     int d;
21 }stps[maxm];
22 
23 int ok[maxn];
24 
25 int Find(int x)
26 {
27     if (pre[x] == x)return x;
28     else
29     {
30         int fa = pre[x];
31         pre[x] = Find(fa);
32         r[x] = (r[x] + r[fa]) % 3;
33         return pre[x];
34     }
35 }
36 bool Union(int x, int y,int d)
37 {
38     int fx = Find(x), fy = Find(y);
39     if (fx == fy)return true;
40     else
41     {
42         pre[fx] = fy;
43         r[fx] = (3 - r[x] + d + r[y]) % 3;
44         return false;
45     }
46 }
47 int main()
48 {
49     while (~scanf("%d%d", &n, &m))
50     {
51         for (int i = 0; i < m; i++)
52         {
53             int u, v,d;
54             char c;
55             scanf("%d%c%d", &u, &c, &v);
56             if (c == '=')d = 0;
57             else if (c == '<') d = 1;
58             else d = 2;
59             stps[i].u = u, stps[i].v=v, stps[i].d=d;
60         }
61         memset(ok, 0, sizeof(ok));
62         for (int i = 0; i < n; i++)
63         {
64             Init();
65             for (int j = 0; j < m; j++)
66             {
67                 if (stps[j].u == i || stps[j].v == i)continue;
68                 if (Union(stps[j].u, stps[j].v, stps[j].d))
69                 {
70                     if ((r[stps[j].u]+3-r[stps[j].v]) % 3 != stps[j].d)
71                     {
72                         ok[i] = j + 1;
73                         break;
74                     }
75                 }
76             }
77         }
78         int cnt = 0,rline=0,judgeperson=0;
79         for (int i = 0; i < n; i++)
80         {
81             if (ok[i]== 0)
82             {
83                 cnt++;
84                 judgeperson = i;
85             }
86             if (ok[i] > rline) rline = ok[i];
87         }
88         if (cnt == 0)printf("Impossible\n");
89         else if (cnt == 1)printf("Player %d can be determined to be the judge after %d lines\n",judgeperson,rline);
90         else printf("Can not determine\n");
91     }
92     return 0;
93 }

View Code

12、hdu 1272 小希的迷宫

  题意:假设有一个通道连通了房间A和B,那么既可以因而它从房间A走到房间B,也得以通过它从房间B走到房间A,为了坚实难度,小希希望任意三个房间有且仅有一条路子可以相通(除非走了回头路)。小希现在把他的安插性图给你,让你帮助判断他的设计图是还是不是吻合她的规划思路。

  思路:并查集。

5588葡京线路 235588葡京线路 24

 1 #include<algorithm>
 2 using namespace std;
 3 const int maxn = 100010;
 4 int pre[maxn];
 5 bool vis[maxn];
 6 int Find(int x)
 7 {
 8     if (pre[x] == x)return x;
 9     else
10     {
11         int fa = pre[x];
12         pre[x] = Find(fa);
13         return pre[x];
14     }
15 }
16 
17 bool Union(int x, int y)
18 {
19     int fx = Find(x), fy = Find(y);
20     if (fx == fy)return true;
21     else
22     {
23         pre[fx] = fy;
24         return false;
25     }
26 }
27 int main()
28 {
29     int u, v;
30     while (~scanf("%d%d", &u, &v))
31     {
32         if (u == -1 && v == -1)break;
33         if (u == 0 && v == 0)
34         {
35             printf("Yes\n");
36             continue;
37         }
38         for (int i = 0; i < maxn; i++)pre[i] = i;
39         bool flag = true;
40         do
41         {
42             if (!flag)continue;
43             if (Union(u, v))
44             {
45                 flag = false;
46             }
47         } while (scanf("%d%d", &u, &v) && u != 0 && v != 0);
48         if (!flag) printf("No\n");
49         else
50         {
51             memset(vis, 0, sizeof(vis));
52             int cnt = 0;
53             for (int i = 0; i < maxn; i++)
54             {
55                 if (pre[i] == i)continue;
56                 int f = Find(i);
57                 if (!vis[f])
58                 {
59                     cnt++;
60                     vis[f] = true;
61                 }
62             }
63             if (cnt == 1) printf("Yes\n");//只能有一个连通块
64             else printf("No\n");
65         }
66     }
67     return 0;
68 }

View Code

13、poj 1308 Is It A Tree

  题意:输入数据表示存在父子节点关系的点的编号,判断是不是为树。

  思路:并查集。

5588葡京线路 255588葡京线路 26

 1 #include<algorithm>
 2 using namespace std;
 3 const int maxn = 100010;
 4 int pre[maxn];
 5 bool vis[maxn];
 6 int Find(int x)
 7 {
 8     if (pre[x] == x)return x;
 9     else
10     {
11         int fa = pre[x];
12         pre[x] = Find(fa);
13         return pre[x];
14     }
15 }
16 
17 bool Union(int x, int y)
18 {
19     int fx = Find(x), fy = Find(y);
20     if (fx == fy)return true;
21     else
22     {
23         pre[fx] = fy;
24         return false;
25     }
26 }
27 int main()
28 {
29     int u, v;
30     int Case = 1;
31     while (~scanf("%d%d", &u, &v))
32     {
33         if (u<0 && v <0)break;
34         if (u == 0 && v == 0)
35         {
36             printf("Case %d is a tree.\n",Case++);
37             continue;
38         }
39         for (int i = 0; i < maxn; i++)pre[i] = i;
40         bool flag = true;
41         do
42         {
43             if (!flag)continue;
44             if (Union(u, v))
45             {
46                 flag = false;
47             }
48         } while (scanf("%d%d", &u, &v) && u != 0 && v != 0);
49         if (!flag) printf("Case %d is not a tree.\n",Case++);
50         else
51         {
52             memset(vis, 0, sizeof(vis));
53             int cnt = 0;
54             for (int i = 0; i < maxn; i++)
55             {
56                 if (pre[i] == i)continue;
57                 int f = Find(i);
58                 if (!vis[f])
59                 {
60                     cnt++;
61                     vis[f] = true;
62                 }
63             }
64             if (cnt == 1) printf("Case %d is a tree.\n", Case++);//只能有一个连通块
65             else printf("Case %d is not a tree.\n",Case++);
66         }
67     }
68     return 0;
69 }

View Code

 14、LA 3644 X-Plosives

5588葡京线路,  题意:给出若干对,表示a和b相连,要确保每个连通块为一颗树,要去除哪些对。

  思路:并查集。

5588葡京线路 275588葡京线路 28

 1 #include<iostream>
 2 using namespace std;
 3 const int maxn = 100100;
 4 int pre[maxn];
 5 int Find(int x)
 6 {
 7     if (x == pre[x]) return x;
 8     else
 9     {
10         int fa = pre[x];
11         pre[x] = Find(fa);
12         return pre[x];
13     }
14 }
15 bool Union(int x, int y)
16 {
17     int fx = Find(x), fy = Find(y);
18     if (fx == fy) return true;
19     else
20     {
21         pre[fx] = fy;
22         return false;
23     }
24 }
25 int main()
26 {
27     int a,b;
28     while (~scanf("%d", &a))
29     {
30         scanf("%d", &b);
31         for (int i = 0; i < maxn; i++) pre[i] = i;
32         Union(a, b);
33         int cnt = 0;
34         while (scanf("%d", &a) && a != -1)
35         {
36             scanf("%d", &b);
37             if (Union(a, b)) cnt++;
38         }
39         printf("%d\n", cnt);
40     }
41     return 0;
42 }

View Code

 15、LA 3027 Corporative Network

  题意:每回可以驾驭一家商厦到其所在的群的主干公司的路线长度,或者将某个群的中坚集团A接到另一个群的某家集团B,并且三个群有着的店家的着力改为本来B所在群的为主公司。

  思路:带权并查集。

5588葡京线路 295588葡京线路 30

 1 #include<iostream>
 2 #include<cmath>
 3 #include<cstdio>
 4 using namespace std;
 5 const int maxn = 20010;
 6 int pre[maxn];
 7 int val[maxn];
 8 int n;
 9 void Init()
10 {
11     for (int i = 0; i <= n; i++) pre[i] = i, val[i] = 0;
12 }
13 int Find(int x)
14 {
15     if (x == pre[x]) return x;
16     else
17     {
18         int fa = pre[x];
19         pre[x] = Find(fa);
20         val[x] = val[x] + val[fa];
21         return pre[x];
22     }
23 }
24 bool Union(int x, int y,int l)
25 {//I x y
26     int fx = Find(x), fy = Find(y);
27     if (fx == fy) return true;
28     else
29     {
30         pre[fx] = fy;
31         val[fx] = l + val[y];
32         return false;
33     }
34 }
35 int main()
36 {
37     int t;
38     scanf("%d", &t);
39     char s[5];
40     while (t--)
41     {
42         scanf("%d", &n);
43         Init();
44         while (~scanf("%s", s))
45         {
46             if (s[0] == 'O')break;
47             if (s[0] == 'E')
48             {
49                 int x;
50                 scanf("%d", &x);
51                 Find(x);
52                 printf("%d\n", val[x]);
53             }
54             else
55             {
56                 int x, y;
57                 scanf("%d%d", &x, &y);
58                 Union(x, y, abs(x - y) % 1000);
59             }
60         }
61     }
62     return 0;
63 }

View Code

 16、LA 4487 Exclusive-OR

  题意:每一遍告诉你A的值是稍稍如故A和B异或的结果是有点,或者通晓k个数连续异或的值。

  思路:带权并查集。

5588葡京线路 315588葡京线路 32

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 using namespace std;
  5 const int maxn = 21000;
  6 int pre[maxn], re[maxn];
  7 int vis[maxn], num[20];
  8 int supperroot = maxn - 10;
  9 void init(int n)
 10 {
 11     for (int i = 0; i <= n + 1; i++)
 12     {
 13         pre[i] = i;
 14         re[i] = 0;
 15         vis[i] = 0;
 16     }
 17     pre[supperroot] = supperroot;
 18     re[supperroot] = 0;
 19 }
 20 int Find(int x)
 21 {
 22     if (x != pre[x])
 23     {
 24         int fa = pre[x];
 25         pre[x] = Find(pre[x]);
 26         re[x] ^= re[fa];
 27     }
 28     return pre[x];
 29 }
 30 bool Union(int x, int y, int val)
 31 {
 32     int fx = Find(x);
 33     int fy = Find(y);
 34     if (fx == fy)
 35     {
 36         if ((re[x] ^ re[y]) != val) return 0;
 37         else return 1;
 38     }
 39     if (fx == supperroot) swap(fx, fy);
 40     pre[fx] = fy;
 41     re[fx] = re[x] ^ re[y] ^ val;
 42     return 1;
 43 }
 44 int main()
 45 {
 46     int n, Q, p, q, val, kase = 0;
 47     char ch[2];
 48     char s[40];
 49     while (scanf("%d%d", &n, &Q))
 50     {
 51         if (n==0&&Q==0) break;
 52         init(n);
 53         printf("Case %d:\n", ++kase);
 54         bool flag = 0;
 55         int facts = 0;
 56         for (int i = 1; i <= Q; i++)
 57         {
 58             scanf("%s", ch);
 59             if (ch[0] == 'I')
 60             {
 61                 facts++;
 62                 gets(s);
 63                 if (sscanf(s, "%d%d%d", &p, &q, &val) == 2)
 64                 {
 65                     val = q; 
 66                     q = supperroot;
 67                 }
 68                 if (flag) continue;
 69                 if (!Union(p, q, val))
 70                 {
 71                     printf("The first %d facts are conflicting.\n", facts);
 72                     flag = 1;
 73                 }
 74             }
 75             else
 76             {
 77                 int k, ans = 0;
 78                 scanf("%d", &k);
 79                 for (int i = 1; i <= k; i++)
 80                 {
 81                     scanf("%d", &num[i]);
 82                     if (flag) continue;
 83                     int fa = Find(num[i]);
 84                     ans ^= re[num[i]];
 85                     num[i] = fa;
 86                     vis[fa] ^= 1;
 87                 }
 88                 if (flag) continue;
 89                 bool unknow = false;
 90                 for (int i = 1; i <= k; i++)
 91                 {
 92                     if (vis[num[i]])
 93                     {
 94                         if (num[i] != supperroot)
 95                         {
 96                             unknow = true;
 97                         }
 98                         vis[num[i]] = 0;
 99                     }
100                 }
101                 if (!unknow) printf("%d\n", ans);
102                 else printf("I don't know.\n");
103             }
104         }
105         printf("\n");
106     }
107     return 0;
108 }

View Code

 17、uva 11987 Almost Union-Find

  题意:第一种操作为把P和Q所在联谊和并,第二种为把结点P放到Q所在集合里,第两种是查询P所在集合的元素数目和总数。

  思路:带权并查集。伊始时把各样结点的先人指向i+n,这样当第三种操作时,就不会影响P原来集合的根。

5588葡京线路 335588葡京线路 34

 1 #include<iostream>
 2 using namespace std;
 3 const int maxn = 100100;
 4 int pre[maxn];
 5 int sum[maxn];
 6 int cnt[maxn];
 7 int n, m;
 8 int Find(int x)
 9 {
10     if (x == pre[x]) return x;
11     else
12     {
13         int fa = pre[x];
14         pre[x] = Find(fa);
15         return pre[x];
16     }
17 }
18 void Union(int x, int y)
19 {
20     int fx = Find(x), fy = Find(y);
21     if (fx != fy)
22     {
23         pre[fx] = fy;
24         sum[fy] += sum[fx];
25         cnt[fy] += cnt[fx];
26         sum[fx] = 0;
27         cnt[fx] = 0;
28     }
29 }
30 void Change(int x, int to)
31 {
32     int f = Find(to);
33     int init = Find(x);
34     pre[x] = f;
35     sum[f] += x, cnt[f]++;
36     sum[init] -= x, cnt[init]--;
37 }
38 int main()
39 {
40     while (~scanf("%d%d", &n, &m))
41     {
42         for (int i = 0; i <= n; i++) pre[i] = i+n, cnt[i+n] = 1, sum[i+n] = i,pre[i+n]=i+n;
43         int s;
44         while (m--)
45         {
46             scanf("%d", &s);
47             if (s == 1)
48             {
49                 int p, q;
50                 scanf("%d%d", &p, &q);
51                 Union(p, q);
52             }
53             else if (s == 2)
54             {
55                 int p, q;
56                 scanf("%d%d", &p, &q);
57                 Change(p, q);
58             }
59             else
60             {
61                 int p;
62                 scanf("%d", &p);
63                 printf("%d %d\n", cnt[Find(p)], sum[Find(p)]);
64             }
65         }
66     }
67     return 0;
68 }

View Code

 18、LA 5898/uva 1493/hdu 4056 Draw a
Mess

  题意:有几多私有根据顺序在n*m的黑板上画4种图形。求最后各样颜色所占的像素数量。

  思路:用并查集维护每行当前岗位的下一个足以画的岗位,然后倒序更新。

5588葡京线路 355588葡京线路 36

 1 #include<cmath>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<cstring>
 6 using namespace std;
 7 
 8 const int maxn = 205;
 9 const int maxm=100500;
10 char str[maxm][25];
11 int xx[maxm], yy[maxm], p[maxm], t[maxm], c[maxm];
12 int Next[maxn][maxm];
13 int Find(int i, int t)
14 {
15     if (Next[i][t] != t)
16         Next[i][t] = Find(i, Next[i][t]);
17     return Next[i][t];
18 }
19 int dele(int i, int l, int r)
20 {
21     int ret = 0;
22     l = Find(i, l);
23     while (l <= r)
24     {
25         ret++;
26         Next[i][l] = l + 1;
27         l = Find(i, l);
28     }
29     return ret;
30 }
31 int main()
32 {
33     int n, m, q;
34     int i, j, x, y, r, w, l, h, color;
35     int tmp1, tmp2, tmp3;
36     int ans[10];
37     while (~scanf("%d%d%d", &n, &m, &q))
38     {
39         for (i = 0; i<n; i++)
40             for (j = 0; j <= m; j++)
41                 Next[i][j] = j;
42         memset(ans, 0, sizeof(ans));
43         for (i = 0; i<q; i++)
44         {
45             scanf("%s%d%d%d%d", str[i], &xx[i], &yy[i], &tmp1, &tmp2);
46             if (str[i][0] != 'R')
47                 p[i] = tmp1, c[i] = tmp2;
48             else
49             {
50                 scanf("%d", &tmp3);
51                 p[i] = tmp1; t[i] = tmp2; c[i] = tmp3;
52             }
53         }
54         for (i = q - 1; i >= 0; i--)
55         {
56             x = xx[i], y = yy[i];
57             if (str[i][0] == 'D')
58             {//菱形
59                 r = p[i], color = c[i];
60                 for (j = max(0, x - r); j <= min(n - 1, x + r); j++)//枚举行
61                     ans[color] += dele(j, max(0, y - r + abs(x - j)),min(m - 1, y + r - abs(x - j)));
62             }
63             else if (str[i][0] == 'T')
64             {//等腰三角形
65                 w = p[i], color = c[i];
66                 h = (w + 1) / 2;
67                 for (j = max(0, x); j<min(n, x + h); j++)
68                     ans[color] += dele(j,max(0, y - h + j - x + 1),min(m - 1, y + h - j + x - 1));
69             }
70             else if (str[i][0] == 'R')
71             {//矩形
72                 l = p[i], w = t[i], color = c[i];
73                 for (j = max(0, x); j <= min(n - 1, x + l - 1); j++)
74                     ans[color] += dele(j, y,min(m - 1, y + w - 1));
75             }
76             else if (str[i][0] == 'C')
77             {//圆形
78                 r = p[i]; color = c[i];
79                 for (j = max(0, x - r); j <= min(n - 1, x + r); j++)
80                 {
81                     int tmp = floor(sqrt(1ll * r*r - (j - x)*(j - x)));
82                     ans[color] += dele(j, max(0, y - tmp), min(m - 1, y + tmp));
83                 }
84             }
85         }
86         for (i = 1; i <= 9; i++)
87         {
88             if (i > 1) printf(" ");
89             printf("%d", ans[i]);
90         }
91         printf("\n");
92     }
93     return 0;
94 }

View Code