HDU/HDOJ 2208 唉,可爱的小朋友(DFS+强连通分支+并查集)

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=2208

有人说用位状态压缩做,等会去试试。

我首先想到的时强连通分支,算出分支数,如果小于气球数,则OK,这里用了并查集的思想。

AC代码:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// Author: Tanky Woo
// Blog:   www.WuTianQi.com
// Problem: HDOJ 2208 唉,可爱的小朋友
#include <iostream>
#include <cmath>
using namespace std;
 
int arr[15][15];
int root[15];
int N, M, K, tmp;
bool finish;
 
void dfs(int n, int m)
{
    if(m > M)
        return;
    if(n == N)
    {
        finish = 1;
        return;
    }
    for(int i=0; i<n; ++i)
    {
        if(root[i] != i)
            continue;
        int flag = 1;
        for(int j=i; j<n && flag; ++j)
            flag = !(root[j]==i && (arr[n][j] == 0 || arr[j][n] == 0));
        if(flag)
        {
            root[n] = i;
            dfs(n+1, m);
            root[n] = n;
        }
    }
    dfs(n+1, m+1);
}
 
bool isOk()
{
    finish = 0;
    for(int i=0; i<N; ++i)
        root[i] = i;
    dfs(0, 0);
    if(finish)
        return 1;
    return 0;
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    while(cin >> N >> M)
    {
        memset(arr, 0, sizeof(arr));
        for(int i=0; i<N; ++i)
        {
            cin >> K;
            for(int j=0; j<K; ++j)
            {
                cin >> tmp;
                arr[i][tmp] = 1;
                //arr[tmp][i] = 1;
            }
        }
        if(M>=N || isOk())
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
 
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDU/HDOJ 2208 唉,可爱的小朋友(DFS+强连通分支+并查集)》有246个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注