UVA 10160 Servicing Stations（深搜 + 剪枝)

Problem D: Servicing stations

A company offers personal computers for sale in N towns (3 <= N <= 35). The towns are denoted by 1, 2, ..., N. There are direct routes connecting M pairs from among these towns. The company decides to build servicing stations in several towns, so that for any town X, there would be a station located either in X or in some immediately neighbouring town of X.

Write a program for finding out the minumum number of stations, which the company has to build, so that the above condition holds.

Input

The input consists of more than one description of town (but totally, less than ten descriptions). Every description starts with number N of towns and number M of pairs of towns directly connected each other. The integers N and M are separated by a space. Every one of the next M rows contains a pair of connected towns, one pair per row. The pair consists of two integers for town's numbers, separated by a space. The input ends with N = 0 and M = 0.

Output

For every town in the input write a line containing the obtained minimum.

An example:

Input:

8 12
1 2
1 6
1 8
2 3
2 6
3 4
3 5
4 5
4 7
5 6
6 7
6 8
0 0

Output:

题意：给定n个城市，m种连接方式，每个城市可以放一个服务站，服务站可以覆盖本城市和与本城市连接的城市。要求最少几个服务站可以覆盖所有城市。

思路：深搜，每个服务站可以选择放与不放服务站。最多35个城市，直接搜最多要搜2^35次，所以要剪枝。。

进行了几个剪枝

1：用邻接表代替邻接矩阵来存放关系。可以减少一点搜索次数。

2：每次找到一个放置方案，保存下个数，如果之后搜索过程中个数超过这个个数。就可以直接结束这次搜索。

3：如果一个点已经搜索过了。并且该点没被覆盖到，并且之后的点没有连接到改点，那么该点永远不会被覆盖到，就可以直接结束这条的搜索。

有一点的要注意的是。标记覆盖不能用单纯的0,1来标记。因为一个点是可以重复覆盖的。我用的是vis[] ++, vis[]--的方法来标记的

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

int n, m;

int x, y;

int snum[40];

int map[40][40];

int f[40];

int minn;

bool cmp(int a, int b)

{

    return a > b;

}

void dfs(int star, int num, int tnum)

{

    if (tnum >= minn)

	return;

    if (num == n)

    {

	minn = tnum;

	return;

    }

    if (star > n)

	return;

    for (int i = 1; i < star; i ++)

	if (!f[i] && map[i][0] < star)

	    return;

    int jia = 0;

    for (int i = 0; i < snum[star]; i ++)

    {

	if (f[map[star][i]] == 0)

	    jia ++;

	f[map[star][i]] ++;

    }

    if (jia)

	dfs(star + 1, num + jia, tnum + 1);

    for (int i = 0; i < snum[star]; i ++)

    {

	f[map[star][i]] --;

    }

    dfs(star + 1, num, tnum);

}

int main()

{

    while (scanf("%d%d", &n, &m) != EOF && n + m)

    {

	minn = n;

	memset(snum, 0, sizeof(snum));

	memset(map, 0, sizeof(map));

	memset(f, 0, sizeof(f));

	for (int i = 0; i < m; i ++)

	{

	    scanf("%d%d", &x, &y);

	    map[x][snum[x] ++] = y;

	    map[y][snum[y] ++] = x;

	}

	for (int i = 1; i <= n; i++)

	{

	    map[i][snum[i] ++] = i;

	    sort(map[i], map[i] + snum[i], cmp);

	}

	dfs(1, 0, 0);

	printf("%d\n", minn);

    }

    return 0;

}

巴特西

UVA 10160 Servicing Stations（深搜 + 剪枝)

Problem D: Servicing stations

An example:

最新文章

热门文章