今天讲了并查集和最小生成树。狠心望弟成龙的学长直接是给拉了两套题。。。做不完做不完，慢慢补咯
The Suspects
Description:
Severe acute respiratory syndrome (SARS), an atypical pneumonia of unknown aetiology, was recognized as a global threat in mid-March 2003. To minimize transmission to others, the best strategy is to separate the suspects from others.
In the Not-Spreading-Your-Sickness University (NSYSU), there are many student groups. Students in the same group intercommunicate with each other frequently, and a student may join several groups. To prevent the possible transmissions of SARS, the NSYSU collects the member lists of all student groups, and makes the following rule in their standard operation procedure (SOP).
Once a member in a group is a suspect, all members in the group are suspects.
However, they find that it is not easy to identify all the suspects when a student is recognized as a suspect. Your job is to write a program which finds all the suspects.
Input
The input file contains several cases. Each test case begins with two integers n and m in a line, where n is the number of students, and m is the number of groups. You may assume that 0 < n <= 30000 and 0 <= m <= 500. Every student is numbered by a unique integer between 0 and n−1, and initially student 0 is recognized as a suspect in all the cases. This line is followed by m member lists of the groups, one line per group. Each line begins with an integer k by itself representing the number of members in the group. Following the number of members, there are k integers representing the students in this group. All the integers in a line are separated by at least one space.
A case with n = 0 and m = 0 indicates the end of the input, and need not be processed.
Output
For each case, output the number of suspects in one line.
Sample Input
100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0
Sample Output
4
1
1
Problem solving:
这道题的意思就是编号为0的学生是有病的，然后告诉你几个组，并且知道如果组里面有一个人是确定有病的，那个这一个组的人都是有病的，问你有病的总共有几个人。
题意理解了题就简单了，就是一个简单的并查集模板问题。但是为了保证你连接的时候用到的最大的那个节点是0，在join(合并函数)里面要加一个判断，保证每次选的最大的父节点是最小的，如果有的话，就可以保证是0了。最后输出父节点是0的个数即可。
Code:
#include<iostream>
#include<cstdio>
using namespace std;
const int sijiaxiaozhu=3e4+10;
int p[sijiaxiaozhu],n,m,k,mi,mii;
int find(int x)
{
return p[x]!=x?p[x]=find(p[x]):x;
}
void join(int x,int y)
{
x=find(x),y=find(y);
if(x<y) p[y]=x;
else p[x]=y;
}
int main()
{
while(~scanf("%d %d",&n,&m))
{
if(n==0&&m==0) break;
for(int i=0;i<n;i++) p[i]=i;
for(int i=0;i<m;i++)
{
scanf("%d %d",&k,&mi);
for(int i=0;i<k-1;i++)
{
cin>>mii;
join(mi,mii);
}
}
int ans=1;
for(int i=1;i<n;i++)
{
find(i);
// cout<<p[i]<<" ";
if(p[i]==0) ans++;
}
cout<<ans<<endl;
}
}畅通工程
Description:
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
Input
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。
注意:两个城市之间可以有多条道路相通,也就是说
3 3
1 2
1 2
2 1
这种输入也是合法的
当N为0时，输入结束，该用例不被处理。
Output
对每个测试用例，在1行里输出最少还需要建设的道路数目。
Sample Input
4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0
Sample Output
1
0
2
998
Huge input, scanf is recommended.
Problem solving:
题意就是告诉你村庄的个数以及哪些村庄之间是通路的。问你现在还需要修几条路才可以使每个村庄都可以连通，无论拐几个弯。
就是一个简单的并查集，有一点难的就是修几条路才可以使村庄全部连通。举个栗子，现在总共四个村庄，1,2是连通的，3,4是连通的。所以现在四个村庄总共被分成了2个部分，此时再多修一条路就可以全部连通了。所以所需修的路的个数就是分成的部分数-1.当一个节点的父节点就是他本身的时候说明这是一个区域。统计父节点与它本身相等的点的个数就是区域的个数。
Code:
#include<bits/stdc++.h>
using namespace std;
const int sijiaxiaozhu=1e5;
int p[sijiaxiaozhu];
int find(int x)
{
return p[x]!=x?p[x]=find(p[x]):x;
}
void join(int x,int y)
{
x=find(x),y=find(y);
if(x!=y) p[x]=y;
}
int main()
{
int n,m,a,b;
while(scanf("%d %d",&n,&m)&&n)
{
int ans=0;
for(int i=1;i<=n;i++) p[i]=i;
for(int i=0;i<m;i++)
{
cin>>a>>b;
join(a,b);
}
for(int i=1;i<=n;i++) if(p[i]==i) ans++;
cout<<ans-1<<endl;
}
}还是畅通工程
Description:
某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。
Output
对每个测试用例，在1行里输出最小的公路总长度。
Sample Input
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0
Sample Output
3
5
Huge input, scanf is recommended.
Problem solving:
题意就是给了你n个村庄，并且给了你N(N-1)/2条路。问你如果想让村庄之间互相连通所需要修的路的最短长度是多少。就是一个简单的最小生成树的模板题。用的Kruscal算法。
Code:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10005;
struct node{
int a,b,c;
}r[maxn];
int p[maxn];
bool cmp(node a,node b)
{
return a.c<b.c;
}
int find(int x)
{
return p[x]!=x?p[x]=find(p[x]):x;
}
void join(int x,int y)
{
x=find(x),y=find(y);
if(x!=y) p[x]=y;
}
int main()
{
int n;
while(scanf("%d",&n)&&n)
{
int sum=0;
for(int i=1;i<=n;i++) p[i]=i;
for(int i=0;i<n*(n-1)/2;i++)
scanf("%d %d %d",&r[i].a,&r[i].b,&r[i].c);
sort(r,r+n*(n-1)/2,cmp);
for(int i=0;i<n*(n-1)/2;i++)
{
if(find(r[i].a)!=find(r[i].b))
{
sum+=r[i].c;
join(r[i].a,r[i].b);
}
}
cout<<sum<<endl;
}
}Ubiquitous Religions
Description:
There are so many different religions in the world today that it is difficult to keep track of them all. You are interested in finding out how many different religions students in your university believe in.
You know that there are n students in your university (0 < n <= 50000). It is infeasible for you to ask every student their religious beliefs. Furthermore, many students are not comfortable expressing their beliefs. One way to avoid these problems is to ask m (0 <= m <= n(n-1)/2) pairs of students and ask them whether they believe in the same religion (e.g. they may know if they both attend the same church). From this data, you may not know what each person believes in, but you can get an idea of the upper bound of how many different religions can be possibly represented on campus. You may assume that each student subscribes to at most one religion.
Input
The input consists of a number of cases. Each case starts with a line specifying the integers n and m. The next m lines each consists of two integers i and j, specifying that students i and j believe in the same religion. The students are numbered 1 to n. The end of input is specified by a line in which n = m = 0.
Output
For each test case, print on a single line the case number (starting with 1) followed by the maximum number of different religions that the students in the university believe in.
Sample Input
10 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
10 4
2 3
4 5
4 8
5 8
0 0
Sample Output
Case 1: 1
Case 2: 7
Hint
Huge input, scanf is recommended.
Problem solving:
题意就是n个学生，m个组，每个组两个人，两个人的宗教信仰是一样的，问你n个学生总共有多少个不同的宗教信仰。简单并查集模板题。
最后查找父节点就是他本身的个数就是答案。
查找的时候别忘了find(i)因为你有可能遇见没有分组的时候对它find的情况，所以你需要在这里find一下避免出现这样的情况导致WA。
Code:
#include<cstdio>
using namespace std;
int n,m,a,b;
const int sijiaxiaozhu=5e4+10;
int p[sijiaxiaozhu];
int find(int x)
{
return p[x]!=x?p[x]=find(p[x]):x;
}
void join(int x,int y)
{
x=find(x),y=find(y);
if(x!=y) p[x]=y;
}
int main()
{
int flag=1;
while(scanf("%d %d",&n,&m))
{
if(n==0&&m==0) break;
for(int i=1;i<=n;i++) p[i]=i;
for(int i=0;i<m;i++)
{
scanf("%d %d",&a,&b);
join(a,b);
}
int ans=0;
for(int i=1;i<=n;i++)
{
find(i);
if(p[i]==i) ans++;
}
printf("Case %d: %d\n",flag++,ans);
}
}
Cube Stacking
Description:
Farmer John and Betsy are playing a game with N (1 <= N <= 30,000)identical cubes labeled 1 through N. They start with N stacks, each containing a single cube. Farmer John asks Betsy to perform P (1<= P <= 100,000) operation. There are two types of operations:
moves and counts.
- In a move operation, Farmer John asks Bessie to move the stack containing cube X on top of the stack containing cube Y.
- In a count operation, Farmer John asks Bessie to count the number of cubes on the stack with cube X that are under the cube X and report that value.
Write a program that can verify the results of the game.
Input
- Line 1: A single integer, P
- Lines 2..P+1: Each of these lines describes a legal operation. Line 2 describes the first operation, etc. Each line begins with a 'M' for a move operation or a 'C' for a count operation. For move operations, the line also contains two integers: X and Y.For count operations, the line also contains a single integer: X.
Note that the value for N does not appear in the input file. No move operation will request a move a stack onto itself.
Output
Print the output from each of the count operations in the same order as the input file.
Sample Input
6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4
Sample Output
1
0
2
Problem solving:
题意就是会有n次操作，每次操作可能有两种情况，一种是M a b就是把第a列的所有方块放在b的上面。另一种就是C a，就是需要输出a下面有几个方块。
带权值的并查集。
这里我用了两个数组进行维护。ans[i]表示i下面方块的个数，now[i]表示i所处的当前列的方块个数。然后如果遇见M这个操作，就把now[a]全部加到now[b]上然后now[a]归零。并且此时ans[find(a)]应该加上now[find(b)].这就实现了把第a列的所有方块放在b上的操作了。
还有就是find函数的写法，在find的过程中，每次查找到的中间的节点的ans的值都应该加到查找开始的ans的值里面。这个不太好解释，也不太好想通。可以在脑子里过一下并查集的操作，并且结合着这道题的做法，好好想想为什么需要加上去。
等我对这个的理解加深的时候再来补上自己成熟的理解。
下面这个图来解释一下这个样例
Code:
#include<iostream>
#include<cstdio>
using namespace std;
const int sijiaxiaozhu=31314;
int p[sijiaxiaozhu],ans[sijiaxiaozhu],now[sijiaxiaozhu];
int find(int x)
{
if(p[x]==x) return p[x];
int mid=p[x];
p[x]=find(p[x]);
ans[x]+=ans[mid];
return p[x];
}
void join(int x,int y)
{
int fx=find(x),fy=find(y);
if(fx==fy) return ;
p[fx]=fy;
ans[fx]+=now[fy];
now[fy]+=now[fx];
now[fx]=0;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=sijiaxiaozhu;i++)
{
now[i]=1;
p[i]=i;
ans[i]=0;
}
for(int i=0;i<n;i++)
{
char s;
int a,b;
cin>>s;
if(s=='M')
{
scanf("%d %d",&a,&b);
join(a,b);
}
else
{
scanf("%d",&a);
find(a);
printf("%d\n",ans[a]);
}
}
}Dragon Balls
Description:
Five hundred years later, the number of dragon balls will increase unexpectedly, so it's too difficult for Monkey King(WuKong) to gather all of the dragon balls together.
His country has N cities and there are exactly N dragon balls in the world. At first, for the ith dragon ball, the sacred dragon will puts it in the ith city. Through long years, some cities' dragon ball(s) would be transported to other cities. To save physical strength WuKong plans to take Flying Nimbus Cloud, a magical flying cloud to gather dragon balls.
Every time WuKong will collect the information of one dragon ball, he will ask you the information of that ball. You must tell him which city the ball is located and how many dragon balls are there in that city, you also need to tell him how many times the ball has been transported so far.
Input
The first line of the input is a single positive integer T(0 < T <= 100).
For each case, the first line contains two integers: N and Q (2 < N <= 10000 , 2 < Q <= 10000).
Each of the following Q lines contains either a fact or a question as the follow format:
T A B : All the dragon balls which are in the same city with A have been transported to the city the Bth ball in. You can assume that the two cities are different.
Q A : WuKong want to know X (the id of the city Ath ball is in), Y (the count of balls in Xth city) and Z (the tranporting times of the Ath ball). (1 <= A, B <= N)
Output
For each test case, output the test case number formated as sample output. Then for each query, output a line with three integers X Y Z saparated by a blank space.
Sample Input
2
3 3
T 1 2
T 3 2
Q 2
3 4
T 1 2
Q 1
T 1 3
Q 1
Sample Output
Case 1:
2 3 0
Case 2:
2 2 1
3 3 2
Problem solving:
这道题最毒瘤的地方绝对是题意。
题目的意思大概就是有n个城市，初始的时候每个城市都有一个龙珠。
现在给你输入几个操作，一种是move，一种是count。move后面有两个数，代表着把第一个数代表的城市的所有的龙珠转移到第二个数代表的城市里面。然后count i的时候需要输出3个数。第一个数代表的是编号为i的龙珠当前所在的城市，第二个数是编号为i的龙珠当前所在城市拥有的龙珠个数，第三个数代表的是编号为i的龙珠移动的次数。
这道题一看就是并查集的问题(如果今天专题不是并查集我可能也想不到)，但这个并不是简单普通的并查集。他要求我们输出的数需要一些巧妙地想法去记录一下。
我们这里用sum[i]来表示第i个城市当前所具有的龙珠个数，p[i]还是并查集里面的p[i]，刚开始的时候初始化每个点的父节点都是自己，每个城市具有的龙珠个数都是1.
在join(合并)的过程中注意，题目要求的是把x的龙珠全部放到y，所以sum[y]+=sum[x],sum[x]=0,这一步这样就挺好理解的了。
然后i所在的城市我们直接输出p[i]就行，i所在的城市的龙珠个数输出sum[i]就行。编号为i的龙珠的移动个数不太好求，那我们怎么求呢？
我们想一下并查集的，就是有点类似于构建一个图的过程。那么每个龙珠移动的次数就正好是它的初始节点距离最大的那个父节点的距离。这道题里面正好每个龙珠的标号就是它的初始节点的编号，所以类似于find函数的查找再查找一遍就能找出它的移动次数了。
（还有一点坑了我就是，不要路径压缩。。。我记得板子是压缩了路径的，然后一直WA，一直WA。。。你需要一个查找距离的过程，如果路径压缩了，那每个移动距离都是1了，会破坏原本的构图。这毒瘤样例也没体现这个坑点。太坑了！！！
Code:
#include<bits/stdc++.h>
using namespace std;
const int sijiaxiaozhu = 1e5;
int p[sijiaxiaozhu],sum[sijiaxiaozhu];
int find(int x)
{
return p[x]!=x?find(p[x]):x;
}
int xiaozhu(int x)//这个就是那个查找移动次数的函数
{
int ans=0;
while(p[x]!=x)//其实跟并查集的find是差不多的的
{
x=p[x];
ans++;//没查找答案一次加一
}
return ans;
}
void join(int x,int y)
{
int fx=find(x),fy=find(y);
if(fx!=fy)
{
p[fx]=fy;
sum[fy]+=sum[fx];//这个就是龙珠转移的过程
sum[fx]=0;
}
}
int main()
{
int t,nu=0;
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
p[i]=i;sum[i]=1;
}
printf("Case %d:\n",++nu);
while(m--)
{
char s[2];
scanf("%s",s);
if(s[0]=='T')
{
int a,b;
scanf("%d %d",&a,&b);
join(a,b);
}
if(s[0]=='Q')
{
int a;
scanf("%d",&a);
printf("%d %d %d\n",find(a),sum[find(a)],xiaozhu(a));
}
}
}
}这个好像是叫带权并查集吧，挺难理解的。但是只要想做，就没有做不出来的题！
Zjnu Stadium
Description:
In 12th Zhejiang College Students Games 2007, there was a new stadium built in Zhejiang Normal University. It was a modern stadium which could hold thousands of people. The audience Seats made a circle. The total number of columns were 300 numbered 1--300, counted clockwise, we assume the number of rows were infinite.
These days, Busoniya want to hold a large-scale theatrical performance in this stadium. There will be N people go there numbered 1--N. Busoniya has Reserved several seats. To make it funny, he makes M requests for these seats: A B X, which means people numbered B must seat clockwise X distance from people numbered A. For example: A is in column 4th and X is 2, then B must in column 6th (6=4+2).
Now your task is to judge weather the request is correct or not. The rule of your judgement is easy: when a new request has conflicts against the foregoing ones then we define it as incorrect, otherwise it is correct. Please find out all the incorrect requests and count them as R.
Input
There are many test cases:
For every case:
The first line has two integer N(1<=N<=50,000), M(0<=M<=100,000),separated by a space.
Then M lines follow, each line has 3 integer A(1<=A<=N), B(1<=B<=N), X(0<=X<300) (A!=B), separated by a space.
Output
For every case:
Output R, represents the number of incorrect request.
Sample Input
10 10
1 2 150
3 4 200
1 5 270
2 6 200
6 5 80
4 7 150
8 9 100
4 8 50
1 7 100
9 2 100
Sample Output
2
Hint
Hint:
（PS： the 5th and 10th requests are incorrect）
Problem solving:
也是一道带权并查集的题，但是我不会。。。代码先贴上来啦，以后再补题解。
Code:
#include<bits/stdc++.h>
using namespace std;
const int sijia=52113;
int f[sijia],sijiaxiaozhu[sijia],n,m;
int find(int x)
{
if(x==f[x]) return f[x];
int t=f[x];
f[x]=find(f[x]);
sijiaxiaozhu[x] += sijiaxiaozhu[t];
return f[x];
}
bool Union(int x,int y,int m)
{
int a=find(x),b=find(y);
if(a==b)
{
if(sijiaxiaozhu[x]+m!=sijiaxiaozhu[y])
return 0;
return 1;
}
f[b]=a;
sijiaxiaozhu[b]=sijiaxiaozhu[x]+m-sijiaxiaozhu[y];
return 1;
}
int main()
{
int a,b,x;
while(~scanf("%d %d",&n,&m))
{
for(int i=0;i<=n;i++)
f[i]=i,sijiaxiaozhu[i]=0;
int cnt=0;
for(int i=0;i<m;i++)
{
scanf("%d %d %d",&a,&b,&x);
if(!Union(a,b,x)) cnt++;
}
printf("%d\n",cnt);
}
}How Many Tables
Description:
Today is Ignatius' birthday. He invites a lot of friends. Now it's dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers.
One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table.
For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least.
Input
The input starts with an integer T(1<=T<=25) which indicate the number of test cases. Then T test cases follow. Each test case starts with two integers N and M(1<=N,M<=1000). N indicates the number of friends, the friends are marked from 1 to N. Then M lines follow. Each line consists of two integers A and B(A!=B), that means friend A and friend B know each other. There will be a blank line between two cases.
Output
For each test case, just output how many tables Ignatius needs at least. Do NOT print any blanks.
Sample Input
2
5 3
1 2
2 3
4 5
5 1
2 5
Sample Output
2
4
Problem solving:
题意我也懒得分析了，就是一个简单并查集，套板子就行了。
Code:
#include<bits/stdc++.h>
using namespace std;
const int sijiaxiaozhu=1e4;
int p[sijiaxiaozhu];
int find(int x)
{
return p[x]!=x?p[x]=find(p[x]):x;
}
void join(int x,int y)
{
x=find(x),y=find(y);
if(x!=y) p[x]=y;
}
int main()
{
int t,n,m,a,b;
scanf("%d",&t);
while(t--)
{
int ans=0;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) p[i]=i;
for(int i=0;i<m;i++)
{
scanf("%d %d",&a,&b);
join(a,b);
}
for(int i=1;i<=n;i++)
{
if(p[i]==i) ans++;
}
printf("%d\n",ans);
}
}
京公网安备 11010502036488号