酷暑一夏1

不忘初心,方得始终


Vijos1022 Victoria的舞会2 题解

题目

Victoria是一位颇有成就的艺术家,他因油画作品《我爱北京天安门》闻名于世界。现在,他为了报答帮助他的同行们,准备开一个舞会。
Victoria准备邀请n个已经确定的人,可是问题来了:
这n个人每一个人都有一个小花名册,名册里面写着他所愿意交流的人的名字。比如说在A的人名单里写了B,那么表示A愿意与B交流;但是B的名单里不见的有A,也就是说B不见的想与A交流。但是如果A愿意与B交流,B愿意与C交流,那么A一定愿意与C交流。也就是说交流有传递性。
Victoria觉得需要将这n个人分为m组,要求每一组的任何一人都愿意与组内其他人交流。并求出一种方案以确定m的最小值是多少。
注意:自己的名单里面不会有自己的名字。

题解

先跑最短路处理出关系,然后将互相可达的加入并查集,统计共有多少个集合即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<cstdio>
#include<cstring>
#include<algorithm>
const int MAXN=200+5;
int want[MAXN][MAXN];int fa[MAXN],a,group,n;
int find(int x){return x==fa[x]?x:find(fa[x]);}
void join(int x,int y){/*printf("Join %d %d\n",x,y);*/int fx=find(x),fy=find(y);if(fx!=fy) fa[fx]=fy;}
int main()
{
scanf("%d",&n);
memset(want,0x3f3f3f,sizeof(want));
for(int i=1;i<=n;i++)
{
fa[i]=i;
while(1)
{
scanf("%d",&a);
if(a) want[i][a]=1; else break;
}
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
want[i][j]=std::min(want[i][j],want[i][k]+want[k][j]);
/*for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
printf("%d\t",want[i][j]);
printf("\n");
}*/
for(int i=1;i<=n;i++)
want[0][i]=0;
// printf("%d\t",want[0][0]);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(want[i][j]!=want[0][0] && want[j][i]!=want[0][0]) join(i,j);
for(int i=1;i<=n;i++)
{
a=find(i);
// printf("%d ",a);
if(!want[0][a]) {group++;want[0][a]=1;}
}
printf("%d",group);
return 0;
}
最近的文章

Vijos1307 黑皮的正方形 题解

题目一天他不务正业出去耍,看见街上的地板是由很多小的正方形组成,顿时心里突发奇想想要总结一下到底有多少正方形。。。。于是乎,他狠下心数了数,终于翻山越岭知道了正方形的总边长为N,你的目的是找出在可以组成的每个至少边为1的正方形的个数。(因为黑皮太笨了,无法找到)。。 题解$f(i)=f(i-1)+i …

于  Vijos, 黑皮的舞蹈 继续阅读
更早的文章

Vijos1415 魔族密码 题解

题目核心部分魔族现在使用一种新型的密码系统。每一个密码都是一个给定的仅包含小写字母的英文单词表,每个单词至少包含1个字母,至多75个字母。如果在一个由一个词或多个词组成的表中,除了最后一个以外,每个单词都被其后的一个单词所包含,即前一个单词是后一个单词的前缀,则称词表为一个词链。例如下面单词组成了一 …

于  Vijos 继续阅读