BZOJ3632 外太空旅行 <随机化>

Posted on Symbols count in article: 649 Reading time ≈ 2 mins.

Problem

外太空旅行

Time Limit: 5Sec5 Sec
Memory Limit: 128MB128 MB

Description

在人类的触角伸向银河系的边缘之际，普通人上太空旅行已经变得稀松平常了。某理科试验班有nn个人，现在班主任要从中选出尽量多的人去参加一次太空旅行活动。
可是nn名同学并不是和平相处的。有的人，比如小AA和小BB整天狼狈为奸，是好朋友；但还有的人，比如杜鲁门和赫鲁晓夫就水火不相容。这nn名同学，由于是理科生，都非常的理性，所以“朋友的朋友就是朋友”和“敌人的朋友就是敌人”这两句话对这些同学无效。换句话说，有可能小AA和小BB是朋友，小BB和小CC是朋友，但是小AA和小CC两人势如水火。
任意两个人之间要不就是敌人，要不就是朋友。
因为在太空船上发生人员斗殴事件是很恶劣也很危险的，因此选出来参加旅行活动的同学必须互相之间都是朋友。你的任务就是确定最多可以选多少人参加旅行。

Input

第一行一个整数nn(1≤n≤501\le n\le 50)。所有的同学按照1∼n1\sim n编号。
接下来若干行，每行两个用空格隔开的整数a,ba, b (1≤a,b≤n1\le a,b\le n)，表示aa和bb是朋友。
注意：如果一个数对(x,y)(x,y)或者(y,x)(y,x)没有在文件中出现，那么编号为xx和yy的两个同学就是敌人。

Output

仅仅一个数，即最多可以选多少人参加活动。

Sample Input

1
2
3
4
5
4
1 2
2 3
3 1
1 4

Sample Output

1
3

说明：选编号为1,2,31,2,3的同学参加，他们互相都是朋友。

标签：最大团 随机化

Solution

一道随机化最大团的裸题。
每次随机出一个1∼n1\sim n的乱序排列，按照排列顺序贪心，这样随机10510^5次取最大值即可。

Code

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
#include <bits/stdc++.h>
#define MAX_N 50
#define BOUND 100000
using namespace std;
int n, seq[MAX_N+5], ans;
bool G[MAX_N+5][MAX_N+5], mrk[MAX_N+5];
int calc() {
    memset(mrk, false, sizeof mrk);
    int ret = 0;
    for (int i = 1; i <= n; i++) if (!mrk[seq[i]]) {
        ret++, mrk[seq[i]] = true;
        for (int j = i+1; j <= n; j++)
            if (!G[seq[i]][seq[j]])	mrk[seq[j]] = true;
    }
    return ret;
}
int main() {
    scanf("%d", &n);	int u, v;
    while (~scanf("%d%d", &u, &v))	G[u][v] = G[v][u] = true;
    for (int i = 1; i <= n; i++)	seq[i] = i;
    for (int i = 0; i < BOUND; i++)
        random_shuffle(seq+1, seq+n+1), ans = max(ans, calc());
    printf("%d", ans);
    return 0;
}