• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

1给定一个nm的矩阵,其中q个位置已经被填充。

2有一个规律,如果(r1,c1)(r1,c1),(r1,c2)(r1,c2)和(r2,c1)(r2,c1)都被填充,那么(r2,c2)(r2,c2)也被填充。其他三个位置生成的任何位置也可以继续生成其他位置。

问一下至少需要人工填充多少元素才能让矩阵充满。

3第一行包含三个整数n,m,q (1 n,m200 000;0qmin(nm,200 000)),

化学表格的尺寸和科学家已经拥有的元素数量。

5以下q行包含两个整数ri,ci (1 ri n,1 ci m),

每一个都描述了科学家已经拥有的元素。输入中的所有元素都不同。

这个想法来自这个大人物:

对书名或背景的注释

我们考虑自动填充的规则,多三个点自动生成第四个点。如果(r1,c1)(r1,c1),(r1,c2)(r1,c2)和(r2,c1)(r2,c1)都被填充,则可视为:

(R1,C1) (R1,C1): R1R1和c1c1相连。

(R1,C2) (R1,C2): R1R1和c2c2相连。

1,21,2 c1c1和c2c2相连。

(R2,C1) (R2,C1): R2R2和c1c1相连。

3,43,4 r2r2和c2c2相连,即(r2,c2)(r2,c2)被填充。

这两个模型是等价的。到目前为止,我们把抽象图中每条边和每列的标号都看作是点,每个给定的点(R,C)都看作是点R和点C属于同一个集合的陈述。因此,我们可以使用并集维护来计算当前矩阵中独立集的个数NN。

考虑需要手动合并的次数(即考虑填充元素的数量)。考虑到当前矩阵中未填充的点,手动填充这个点当然可以实现两个集合的合并,即集合总数减少1。所有可以自动填充的点在每次手动填充后都会自动填充。因此,经过n1次人工填充后,它们都将属于一个集合,矩阵将被填充,所以原问题的答案是N1。

————————————————

版权声明:本文为CSDN博主“hyp1231”原创文章,遵循CC 4.0 BY-SA版权协议。转载请附上原始来源和本声明的链接。

原文链接:https://blog.csdn.net/hyp1231/article/details/81295464

1 #包括iostream

2 #包括cstring

3 #包含算法

4使用命名空间std

5 const int N=2 * 1e5 10

6 int p[N * 2];

7 int n,m,q;

8 int find(int x)

9 {

10 if (p[x]!=x)

11 p[x]=find(p[x]);

12返回p[x];

13 }

14 int main()

15 {

16 int r,c;

17 scanf('%d%d%d ',n,m,q);

18 for(int I=1;I=n m;I)p=I;

19 while (q -)

20 {

21 scanf('%d%d ',r,c);

22 int fr=find(r),fc=find(c n);//最好说一下c ^ n:我们用序列1~n标注每一行,为了不重复,从n ^ 1开始用:标注每一列。

//最多n m,正好m列,对应n ^ 1 ~ n ^ m,m个元素。

23 if (fr!=fc)

24p[fc]=fr;

25 }

26 int ans=0;

27 for(int I=1;I=n m;我)

28 {

2IF(P==I)//当ans为nn时,nn=2时,从中取两个元素ai,aj,表示(ai,aj)这个点一定不存在,否则即使p[ai]==ai,p[aj]应该==ai;

//所以我们要手动添加这个点;当nn2,也就是nn=1时,这一定是所有联通的情况,是所有的爷爷。

30 ans

31 }

32如果(ans==0)

33 printf('%d ',ans);

其他34个

35 printf('%d ',ans-1);

36返回0;

37 }

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now