一本通 P1386 【打击犯罪】

题库：一本通
题号：1386
题目：打击犯罪
link ：http://ybt.ssoier.cn:8088/problem_show.php?pid=1386

O(n³)思路：此题数据太水，n³就能卡过。暴力枚举1 ~ n，每次都重新将并查集初始化并且按题目输入将所有 >= k(1 <= k <= n)的点合并（及打击掉1 ~ k的犯罪团伙，他们不合并）。从1 ~ n枚举直到找到最小的k满足所有犯罪团伙中的最大的一个的危险程度不超过n / 2，直接输出k。

code ：

 1 #include <bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 using namespace std;
 4 int n, fa[1001], size[1001], p[1001], q[1001][1001];//记录下输入数据 
 5 inline int find(int x)//搜索 
 6 {
 7     return x == fa[x] ? fa[x] : fa[x] = find(fa[x]);
 8 }
 9 inline void unity(int x, int y)//按秩合并 + 路径压缩 
10 {
11     int r1 = find(x);
12     int r2 = find(y);
13     if(size[r1] < r2)
14     {
15         fa[r1] = r2;
16         size[r2] += size[r1];
17     }
18     else
19     {
20         fa[r2] = r1;
21         size[r1] += size[r2];
22     }
23     return;
24 }
25 inline void init(int x)
26 {
27     for(register int i = 1; i <= n; ++i)
28     {
29         fa[i] = i;
30         size[i] = 1;
31     }
32     for(register int i = x + 1; i <= n; ++i)//重新将没被打击掉的犯罪团伙之间的联系连接起来 
33     {
34         for(register int j = 1; j <= p[i]; ++j)
35         {
36             if(q[i][j] > x && find(i) != find(q[i][j]))//被联系的犯罪团伙也得 > x 
37             {
38                 unity(i, q[i][j]);
39             }
40         }
41     }
42     return;
43 }
44 inline int check()//判断犯罪团伙中最大的一个是否 > n / 2 
45 {
46     for(register int i = 1; i <= n; ++i)
47     {
48         if(size[fa[i]] > n / 2)
49         {
50             return 0;
51         }
52     }
53     return 1;
54 }
55 signed main()
56 {
57     scanf("%d", &n);
58     for(register int i = 1; i <= n; ++i)
59     {
60         scanf("%d", &p[i]);
61         for(register int j = 1; j <= p[i]; ++j)
62         {
63             scanf("%d", &q[i][j]);
64         }
65     }
66     for(register int i = 0; i <= n; ++i)
67     {
68         init(i);//初始化 
69         if(check())//判断 
70         {
71             printf("%d", i);
72             return 0;
73         }
74     }
75     return 0;
76 }

O(n²)正解思路：我们发现每次都重新输入过于多余，可以倒着输入，判断犯罪团伙中最大的一个是否 > n / 2，直到犯罪团伙中最大的一个 > n / 2时，输出k(k从n ~ 1枚举)，表示不打击掉k就不行了。

code ：

 1 //和O(n ^ 3)的注释基本差不多 
 2 #include <bits/stdc++.h>
 3 #define INF 0x3f3f3f3f
 4 using namespace std;
 5 int n, fa[1001], size[1001], p[1001], q[1001][1001];
 6 inline int find(int x)
 7 {
 8     return x == fa[x] ? fa[x] : fa[x] = find(fa[x]);
 9 }
10 inline void unity(int x, int y)
11 {
12     int r1 = find(x);
13     int r2 = find(y);
14     if(size[r1] < r2)
15     {
16         fa[r1] = r2;
17         size[r2] += size[r1];
18     }
19     else
20     {
21         fa[r2] = r1;
22         size[r1] += size[r2];
23     }
24     return;
25 }
26 inline void init(int x)
27 {
28     for(register int i = 1; i <= p[x]; ++i)
29     {
30         if(q[x][i] >= x && find(x) != find(q[x][i]))
31         {
32             unity(x, q[x][i]);
33         }
34     }
35     return;
36 }
37 inline int check()
38 {
39     for(register int i = 1; i <= n; ++i)
40     {
41         if(size[fa[i]] > n / 2)
42         {
43             return 0;
44         }
45     }
46     return 1;
47 }
48 signed main()
49 {
50     scanf("%d", &n);
51     for(register int i = 1; i <= n; ++i)
52     {
53         fa[i] = i;
54         size[i] = 1;
55     }
56     for(register int i = 1; i <= n; ++i)
57     {
58         scanf("%d", &p[i]);
59         for(register int j = 1; j <= p[i]; ++j)
60         {
61             scanf("%d", &q[i][j]);
62         }
63     }
64     for(register int i = n; i >= 1; --i)//倒着整 
65     {
66         init(i);
67         if(!check())//如果不打击掉当前犯罪团伙就不行了 
68         {
69             printf("%d", i);//最小打击值 
70             return 0;
71         }
72     }
73     return 0;
74 }