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:

2

状态压缩+dfs剪枝

之前没怎么了解状态压缩,真心感觉状态压缩强大,还是自己了解太少~

 

#include <cstdio>
using namespace std;
int n,m;
long long st[36],plu[36];
bool dfs(long long state,int step,int begin,int len)
{
    if(state==((((long long)1)<<n)-1)) return true;
    if(step==len||begin>n) return false;//剪枝
    //if(begin>n) return false;//剪枝
    for(int i=begin;i<=n;i++)
    {
        if((state|plu[i])!=(((long long)1)<<n)-1) break;
        if((st[i]|state)==state) continue;
        if(dfs(state|st[i],step+1,i+1,len))
          return true;
    }
    return false;
}
int main()
{

     while(scanf("%d%d",&n,&m),n||m)
     {
         for(int i=1;i<=n;i++)//初始化
         {
             plu[i]=0;
             st[i]=(((long long)1)<<(i-1));
         }
         int a,b;
         for(int i=1;i<=m;i++)
         {
             scanf("%d%d",&a,&b);
             st[a]|=(((long long)1)<<(b-1));
             st[b]|=(((long long)1)<<(a-1));
         }
         plu[n]=st[n];
         for(int i=n-1;i>=1;i--)
           plu[i]=(st[i]|plu[i+1]);
        for(int i=1;i<=n;i++)
        {
            //state=0;
            if(dfs(0,0,1,i))
            {
                printf("%d\n",i);
                break;
            }
        }
     }
     return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation