Servicing Stations

Servicing Stations

时间: 1ms        内存:64M

描述:

A company offers personal computers for sale in N towns ( 3<=N<=35), denoted by 1, 2,..., N. There are direct routes connecting M pairs among these towns. The company decides to build servicing stations to ensure that for any town X, there will be a station located either in X or in some immediately neighboring town of X. Write a program to find the minimum number of stations the company has to build.

输入:

The input consists of multiple problem descriptions. Every description starts with number of towns N and number of town-pairs M, separated by a space. Each of the next M lines contains a pair of integers representing connected towns, at one pair per line with each pair separated by a space. The input ends with N = 0 and M = 0.

输出:

For each input case, print a line reporting the minimum number of servicing stations needed.

示例输入:

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

示例输出:

2

提示:

参考答案(内存最优[1276]):

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector < long long unsigned > edge;
bool finish;
int minimum;
long long unsigned end_tag;
long long unsigned origin_tag;

void check(int flag[], int position)
{
	long long unsigned tag = origin_tag, origin = tag;
	int index = 0;
	for (int i = 0; i < edge.size(); i++)
	{
		if ((index < position) && (flag[index] == i))
		{
			tag |= edge[i];
			if (tag > origin)
				origin = tag;
			else
				return;
			index++;
		}
	}
	
	if (tag == end_tag)
	{
		finish = true;
		minimum = index;
	}
}

void generate(int flag[], int position, int positions)
{
	if (finish)
		return;

	if (position < positions)
	{
		if (position == 0)
		{
			for (int i = 0; i < edge.size(); i++)
			{
				flag[position] = i;
				generate(flag, position + 1, positions);
			}
		}
		else
		{
			for (int i = flag[position - 1] + 1; i < edge.size(); i++)
			{
				flag[position] = i;
				generate(flag, position + 1, positions);
			}
		}
	}
	else
		check(flag, position);
}

void backtrack()
{
	finish = false;

	for (int i = 1; i <= edge.size(); i++)
	{
		int * flag = new int[edge.size()];
		generate(flag, 0, i);
		delete [] flag;
		
		if(finish)
			return;
	}
}

bool cmp(long long unsigned x, long long unsigned y)
{
	return x > y;
}

int main(int ac, char *av[])
{
	int n;
	int m;
	int x, y;
	vector < vector < int > > tmp;
	
	while (cin >> n >> m, n && m)
	{
		tmp.clear();
		tmp.resize(n);
		
		for (int i = 0; i < m; i++)
		{
			cin >> x >> y;
			if (x != y)
			{
				tmp[x - 1].push_back(y);
				tmp[y - 1].push_back(x);
			}
		}
		
		int base = 0;
		origin_tag = 0;
		end_tag = 0;
		
		vector < bool > tag;
		tag.resize(n);
		fill(tag.begin(), tag.end(), false);
		
		for (int i = 0; i < tmp.size(); i++)
		{
			if (tmp[i].size() == 0)
			{
				base++;
				origin_tag |= ((long long unsigned)1 << i);
			}
			
			if (tmp[i].size() == 1 && tag[i] == false)
			{
				tag[i] = true;
				if (tag[tmp[i][0] - 1] == false)
				{
					base++;
					tag[tmp[i][0] - 1] = true;
				}
			}

			end_tag |= ((long long unsigned)1 << i);
		}

		edge.clear();
		for (int i = 0; i < tmp.size(); i++)
		{
			if (tag[i] == true)
			{
				origin_tag |= ((long long unsigned)1 << i);
				for (int j = 0; j < tmp[i].size(); j++)
					origin_tag |= ((long long unsigned)1 << (tmp[i][j] - 1));
				
			}
			
			if (tag[i] == false && tmp[i].size() > 0)
			{
				long long unsigned t = ((long long unsigned)1 << i);
				for (int j = 0; j < tmp[i].size(); j++)
					t |= ((long long unsigned)1 << (tmp[i][j] - 1));
				edge.push_back(t);
			}
		}
		
		sort(edge.begin(), edge.end(), cmp);
		
		minimum = 0;
		backtrack();
		
		cout << base + minimum << endl;
	}

	return 0;
}

参考答案(时间最优[320]):

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector < long long unsigned > edge;
bool finish;
int minimum;
long long unsigned end_tag;
long long unsigned origin_tag;

void check(int flag[], int position)
{
	long long unsigned tag = origin_tag, origin = tag;
	int index = 0;
	for (int i = 0; i < edge.size(); i++)
	{
		if ((index < position) && (flag[index] == i))
		{
			tag |= edge[i];
			if (tag > origin)
				origin = tag;
			else
				return;
			index++;
		}
	}
	
	if (tag == end_tag)
	{
		finish = true;
		minimum = index;
	}
}

void generate(int flag[], int position, int positions)
{
	if (finish)
		return;

	if (position < positions)
	{
		if (position == 0)
		{
			for (int i = 0; i < edge.size(); i++)
			{
				flag[position] = i;
				generate(flag, position + 1, positions);
			}
		}
		else
		{
			for (int i = flag[position - 1] + 1; i < edge.size(); i++)
			{
				flag[position] = i;
				generate(flag, position + 1, positions);
			}
		}
	}
	else
		check(flag, position);
}

void backtrack()
{
	finish = false;

	for (int i = 1; i <= edge.size(); i++)
	{
		int * flag = new int[edge.size()];
		generate(flag, 0, i);
		delete [] flag;
		
		if(finish)
			return;
	}
}

bool cmp(long long unsigned x, long long unsigned y)
{
	return x > y;
}

int main(int ac, char *av[])
{
	int n;
	int m;
	int x, y;
	vector < vector < int > > tmp;
	
	while (cin >> n >> m, n && m)
	{
		tmp.clear();
		tmp.resize(n);
		
		for (int i = 0; i < m; i++)
		{
			cin >> x >> y;
			if (x != y)
			{
				tmp[x - 1].push_back(y);
				tmp[y - 1].push_back(x);
			}
		}
		
		int base = 0;
		origin_tag = 0;
		end_tag = 0;
		
		vector < bool > tag;
		tag.resize(n);
		fill(tag.begin(), tag.end(), false);
		
		for (int i = 0; i < tmp.size(); i++)
		{
			if (tmp[i].size() == 0)
			{
				base++;
				origin_tag |= ((long long unsigned)1 << i);
			}
			
			if (tmp[i].size() == 1 && tag[i] == false)
			{
				tag[i] = true;
				if (tag[tmp[i][0] - 1] == false)
				{
					base++;
					tag[tmp[i][0] - 1] = true;
				}
			}

			end_tag |= ((long long unsigned)1 << i);
		}

		edge.clear();
		for (int i = 0; i < tmp.size(); i++)
		{
			if (tag[i] == true)
			{
				origin_tag |= ((long long unsigned)1 << i);
				for (int j = 0; j < tmp[i].size(); j++)
					origin_tag |= ((long long unsigned)1 << (tmp[i][j] - 1));
				
			}
			
			if (tag[i] == false && tmp[i].size() > 0)
			{
				long long unsigned t = ((long long unsigned)1 << i);
				for (int j = 0; j < tmp[i].size(); j++)
					t |= ((long long unsigned)1 << (tmp[i][j] - 1));
				edge.push_back(t);
			}
		}
		
		sort(edge.begin(), edge.end(), cmp);
		
		minimum = 0;
		backtrack();
		
		cout << base + minimum << endl;
	}

	return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

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