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;
}题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。