2020牛客暑期多校训练营（第四场）I Investigating Legions 题解

题意：

给你一个 n 个点的图的邻接矩阵 ( n<=300 ) ，其中每个元素都有 1/S (20<=S<=100) 的几率出错，要求复原原图中那些点是在一个连通块里的。

QAQ正解不懂啊QAQ……

所以我学会了乱搞。

由于出错的几率最大只有 1/20 ，我们可以大胆猜想出错的其实很少，所以我们对于一个还没确定连通块的点如下操作：

找到与他相连的所有点，总计cnt个。

对所有没确定连通块的点进行遍历，如果与这些点相连大于等于cnt/2就把他算到这个连通块里。

（论乱搞的重要性

 1 #include<iostream>
 2 #include<cstdlib>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<algorithm>
 7 #define N 305
 8 using namespace std;
 9 int T,n,S,cnt,tmp[N],cnt1;
10 bool ma[N][N];
11 char BB[N*N];
12 int fw[N];
13 int main()
14 {
15     scanf("%d",&T);
16     while(T--)
17     {
18         scanf("%d%d",&n,&S);
19         scanf("%s",BB+1);
20         cnt=0;
21         cnt1=-1;
22         memset(fw,-1,sizeof(fw));
23         for(int i=1;i<=n;i++)
24         {
25             for(int j=i+1;j<=n;j++)
26             {
27                 cnt++;
28                 ma[i][j]=ma[j][i]=(BB[cnt]=='1');
29             }
30             ma[i][i]=1; 
31         }
32         
33         for(int i=1;i<=n;i++)
34         {
35             if(fw[i]==-1)
36             {
37                 cnt=0;
38                 for(int j=1;j<=n;j++)
39                 {
40                     if(fw[j]==-1&&ma[i][j])
41                     {
42                         cnt++;
43                         tmp[cnt]=j;
44                     }
45                 }
46                 cnt1++;
47                 int sum=0;
48                 for(int j=1;j<=n;j++)
49                 {
50                     if(fw[j]==-1)
51                     {
52                         sum=0;
53                         for(int k=1;k<=cnt;k++)
54                         {
55                             if(ma[j][tmp[k]])
56                             {
57                                 sum++;
58                             }
59                         }
60                         if(sum>=cnt/2) fw[j]=cnt1;
61                         
62                     }
63                 }
64             }
65         }
66         for(int i=1;i<=n;i++)
67         {
68             printf("%d ",fw[i]);
69         }
70         printf("
");
71     }
72     return 0;
73 }

View Code