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;
    }
 
}

HDU/HDOJ 1015 Safecracker

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

分析:DFS。

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
73
74
75
76
77
78
79
80
81
82
83
84
85
/*
  Description:HDOJ 1015
  Author: Tanky Woo
  Blog:   www.WuTianQi.com
  Date: 19-01-11 22:08
  Note:  转载请保留作者信息
*/
 
#include <iostream>
#include <algorithm>
using namespace std;
 
int tar;
char str[15];
char ans[6];
char wtq[6];
int len;
bool s[15];
bool flag ;
 
int cal(char num, int k)
{
    int t = 1;
    for(int i=1; i<=k; ++i)
        t *= (num-'A'+1);
    return t;
}
 
int cmp(char a, char b)
{
    return a>b;
}
 
 /*
int cmp(const void *a,const void *b)
{
 return *(char *)b-*(char *)a;
}
*/
void TK(int n)
{
    if(n == 5)
    {
        int num = cal(ans[0], 1) - cal(ans[1],2) + cal(ans[2],3) - cal(ans[3],4) + cal(ans[4],5);
        if(num == tar)
        {
            strcpy(wtq, ans);
            flag = 1;
        }
        return;
    }
    for(int j=0; j<len; ++j)
        if(s[j] == 0)
        {
             ans[n] = str[j];
             s[j] = 1;
             TK(n+1);
             if(flag == 1)
                return;
             s[j] = 0;
        }
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
   while(scanf("%d %s", &tar, str) && !((tar==0)&&(strcmp(str, "END")==0))) 
   {
        memset(s, 0, sizeof(s));
        memset(ans, 0, sizeof(ans));
        memset(wtq, 0, sizeof(wtq));
        flag = 0;
        len = strlen(str);
        sort(str, str+len, cmp);
        //qsort(str, len, sizeof(str[0]),cmp);
        TK(0);
        if(flag)
           cout << wtq << endl;
        else
           cout << "no solution\n";
 
   }
    return 0;
}

先前一直WA,经过miyu提醒才知道。原来我把sort返回值和qsort搞混了。

qsort返回-1,0,1

sort返回0, 1

所以qsort要用减号(-)来比较,而sort用大于号(>)比较。

HDOJ 1010 Tempter of the Bone

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

第一次写剪枝的题目。
这里用了几次剪枝。
先贴出代码再说:

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
73
74
75
76
77
78
79
#include <iostream>
using namespace std;
 
 
char maze[8][8];
int dir[4][2] = {{0,-1}, {0,1}, {1,0}, {-1,0}};
int N, M, T;
int stax, stay, endx, endy;
int steps;
bool escape;
void DFS(int x, int y, int cnt)
{
	if(x>N || y>M || x<1 || y<1)        //剪枝3
		return;
	if(cnt==T && x==endx && y==endy)
		escape = 1;
	if(escape == 1)
		return;
	int temp = (T-cnt) - abs(x-endx) - abs(y-endy);
	if(temp<0 || temp&1)    //剪枝2
		return;
	for(int i=0; i<4; ++i)
	{
		if(maze[x+dir[i][0]][y+dir[i][1]] != 'X')
		{
			maze[x+dir[i][0]][y+dir[i][1]] = 'X';
			DFS(x+dir[i][0], y+dir[i][1], cnt+1);
			maze[x+dir[i][0]][y+dir[i][1]] = '.';
		}
	}
	return;
}
 
int main()
{
	//freopen("input.txt", "r", stdin);
	while(scanf("%d %d %d", &N, &M, &T) && (N+M+T))
	{
		getchar();
		//printf("%d %d %d\n", N, M, T);
		escape = 0;
		steps = 0;
		stax = stay = endx = endy = 0;
		for(int i=1; i<=N; ++i)
		{
			for(int j=1; j<=M; ++j)
			{
				scanf("%c", &maze[i][j]);
				//printf("%c", maze[i][j]);
				if(maze[i][j] == 'S')
				{
					stax = i;
					stay = j;
				}
				if(maze[i][j] == 'D')
				{
					endx = i;
					endy = j;
				}
				if(maze[i][j] == 'X')
					steps++;
			}
			getchar();
			//printf("\n");
		}
		if(T >= M*N - steps)   //剪枝1
		{
			printf("NO\n");
			continue;
		}
		maze[stax][stay] = 'X';
		DFS(stax, stay, 0);
		if(escape == 1)
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}

剪枝一:
对于可以走的最多步数比开门还要小,当然要剪掉。

剪枝二:
奇偶剪枝:
可以把map看成这样:
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
从为 0 的格子走一步,必然走向为 1 的格子
从为 1 的格子走一步,必然走向为 0 的格子
即:
0 ->1或1->0 必然是奇数步
0->0 走1->1 必然是偶数步
结论:
所以当遇到从 0 走向 0 但是要求时间是奇数的,或者,
从 1 走向 0 但是要求时间是偶数的 都可以直接判断不可达!

剪枝三:
边界条件。

剪枝无处不在,请看剪枝相关资料:
传送门:http://www.wutianqi.com/?p=1341

搜索与剪枝

半年前在POJ上遇到过一次剪枝的题目,那时觉得剪枝好神秘。。。今天在网上查了半天资料,终于还是摸索到了一点知识,但是相关资料并不多,在我看来,剪枝是技巧,而不是方法,也就是说,可能一点实用的小技巧,让程序可以少判断一点,这就是剪枝,剪枝无处不在。

搜索的进程可以看作是从树根出发,遍历一棵倒置的树—-搜索树的过程。而所谓的剪枝,顾名思义,就是通过某种判断,避免一些不必要的遍历过程,形象的说,就是减去了搜索树中的某些“枝条”,故称剪枝。
(杭电课件上是这么说的:即剪去解答树上已被证明不可能存在可行解或最优解的子树.)

既然采用了搜索,剪枝就显得十分的必要,即使就简简单单的设一个槛值,或多加一两条判断,就可对搜索的效率产生惊人的影响。例如N后问题,假如放完皇后再判断,则仅仅只算到7,就开始有停顿,到了8就已经超过了20秒,而如果边放边判断,就算到了10,也没有停顿的感觉。所以,用搜索一般都就要剪枝。

剪枝至少有两方面,一是从方法上剪枝,如采用分枝定界,启发式搜索等,适用范围比较广;二是使用一些小技巧,这类方法适用性虽不如第一类,有时甚至只能适用一道题,但也十分有效,并且几乎每道题都存在一些这样那样的剪枝技巧,只是每题有所不同而已。

剪枝的原则:
1.正确性:必须保证不丢失正确的结果。
2.准确性:能够尽可能多的减去不能通向正解的枝条
3.高效性:在很多时候,为了加强优化的效果,我们会增加一些判断,这样对程序效率也带来了副作用,所以要考虑剪枝的高效性,否则得不偿失。

最后说一下:剪枝在搜索中用的是非常的广泛的。

参照杭电课件第47页一句话:
ACMer们:
为了ACM事业,努力地剪枝吧!!

题目我不多说,HDOJ 1010就是一个很好的剪枝题目。
另外,杭电的课件–搜索篇里面也讲了搜索与剪枝。