游客 注册 | 登录
中文 | En

1968 - 游花园

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 32 MB

ACMCLUB的花园有n种花，每种花都种在不同的地点，地点分别用1到n表示。不同的花之间可能有路，也可能没路，花园一共有m条路。现在小明想要从1开始走，把每种花都看一遍，且每种花仅看一遍，最后到达终点n，请写出程序判断小明能否实现目标。

题目输入

测试数据有多组。

每组输入的第一行为整数n(n<=20)，接下来一行输入一个数字m，表示有m条路。再接下来输入m行，每行输入两个数字x和y，表示x与y有路相连，每条路都是双向可走的。数据保证不会有重复的路。

题目输出

对于每组测试数据输出一行，如果小明能够实现目标，则输出1，否则输出0。

输入/输出样例

输入格式

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

输出格式

0
1

C语言解答

#include<stdio.h>
#include<string.h>

int map[21][21] = {0}, vis[21] = {0}, n, flag = 0, m;
void dfs(int start, int num)
{
	int i;	
	if( num == n - 1 && start == n)
		flag=1;
	if(flag==1)
		return;
	for(i=2;i<=n;++i)
		if(vis[i]!=1&&map[start][i]!=0){
			vis[i]=1;
			dfs(i,num+1);
			vis[i]=0;
		}

}

int main()
{
	
	while(scanf("%d%d", &n, &m) != EOF)
	{
		int i, j;
		memset(map, 0, sizeof(map));
		memset(vis, 0, sizeof(vis));
		for( i = 0; i < 21; i++)
		{
			vis[i] = 0;
			for( j = 0; j < 21; j++)
				map[i][j] = 0;
		}
		flag = 0;
		while(m--)
		{
			int a, b;
			scanf("%d%d", &a, &b);
			map[a][b] = 1;
			map[b][a] = 1;
		}
		dfs(1, 0);
		if(flag)
			printf("1\n");
		else
			printf("0\n");
	}
	return 0;
	
}

C++解答

#include <cstdio>
#include <vector>
using namespace std;

int ed, n;
vector < vector < int > > v;

bool dfs(int x, int s) {
    if (s == ed)
        return x == n - 1;
    for (vector < int >::iterator it = v[x].begin(); it != v[x].end(); ++it)
        if (~s >> *it & 1)
            if (dfs(*it, s | (1 << *it)))
                return true;
    return false;
}

int main() {
    int m;
    while (EOF != scanf("%d%d", &n, &m)) {
        v = vector < vector < int > >(n);
        ed = (1 << n) - 1;
        while (m--) {
            int x, y;
            scanf("%d %d", &x, &y);
            --x; --y;
            v[x].push_back(y);
            v[y].push_back(x);
        }
        printf("%d\n", dfs(0, 1));
    }
    return 0;
}
请先登陆