首页 > 代码库 > UVA10160 Servicing Stations
UVA10160 Servicing Stations
题目大意：
有n个城市（n<=35）,其中某些城市有边相连。如果在某一点放一个发电站，与他直接相邻的城市就可以得到供电。
虽然题目说的是有向图，但是实际上处理的时候是无向图。这是根据样例分析出来的。
换种理解就是求一幅无向图的最小支配集。也就是在图中找到点数最少的一个点集，使得其他所有的点都和点集中点（一个或多个）有边相连。
参考博客：http://blog.csdn.net/hackerwin7/article/details/16344839
题目分析：
NP问题，但数据量小，只有35个顶点，所以可以暴力枚举。也就是每一顶点有选和不选两种可能，最后应该有235种可能。这肯定会超时，所以需要剪枝。
剪枝的情况是：
1、当前的发电站个数大于当前所需最少的发电站个数。这样已经没必要进行下去了，因为不可能产生更优的解。
2、如果在某一点放发电站以后，通电的城市的个数没有增加，也不用再继续了。
3、枚举第k点的时候，如果它前面的点（1 ~ k-1）存在不通电的城市x，并且后面的点（k ~ n）中不存在与x相邻的点，也不用再继续了。原因是x这个点(城市)怎么也不可能通电。它本身不能放发电站(枚举的就是它不放发电站的情况)，其后面的点又不能为它供电。
下面是丑陋的代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 7 const int N = 40; 8 int n,m; 9 bool Map[N][N];10 int vis[N];11 int s,Min,num;//s是发电站个数，num通电的城市的数量12 void dfs(int cur)13 {14 if(s>Min) return ;//第一种情况的剪枝15 if(cur>n)16 {17 if(num==n) Min=min(Min,s);18 }19 else20 {21 //第三种情况的剪枝22 int i,j;23 for(i=1;i<cur;i++)24 {25 if(!vis[i])26 {27 for(j=cur;j<=n;j++)28 if(Map[i][j]) break;29 if(j>n) return;30 }31 }32 //cur位置放发电站33 int k=num;34 if(!vis[cur]) num++;35 vis[cur]++;36 s++;37 for(i=1;i<=n;i++)38 {39 if(Map[cur][i])40 {41 if(!vis[i]) num++;42 vis[i]++;43 }44 }45 if(num>k) //第二种情况的剪枝46 dfs(cur+1);47 //cur位置不放发电站48 for(i=1;i<=n;i++)49 {50 if(Map[cur][i])51 {52 vis[i]--;53 if(!vis[i]) num--;54 }55 }56 s--;57 vis[cur]--;58 if(!vis[cur]) num--;59 dfs(cur+1);60 }61 }62 int main()63 {64 //freopen("test.txt","r",stdin);65 while(scanf("%d%d",&n,&m)!=EOF&&n)66 {67 memset(vis,0,sizeof(vis));68 memset(Map,0,sizeof(Map));69 int a,b;70 while(m--)71 {72 scanf("%d%d",&a,&b);73 Map[a][b]=Map[b][a]=1;74 }75 Min=35;76 s=0;77 num=0;78 dfs(1);79 printf("%d\n",Min);80 }81 return 0;82 }
PS：感觉剪枝非常需要分析能力。脑袋不够用了。
UVA10160 Servicing Stations
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。