澳门新葡亰8455下载app-网站注册正规靠谱 > 产品展示 >
但是实际上处理的时候是无向图

题目大意:

  有n个城市(n<=35),其中某些城市有边相连。如果在某一点放一个发电站,与他直接相邻的城市就可以得到供电。

  虽然题目说的是有向图,但是实际上处理的时候是无向图。这是根据样例分析出来的。

  换种理解就是求一幅无向图的最小支配集。也就是在图中找到点数最少的一个点集,使得其他所有的点都和点集中点(一个或多个)有边相连。

  

参考博客:

 

题目分析:

  NP问题,但数据量小,只有35个顶点,所以可以暴力枚举。也就是每一顶点有选和不选两种可能,最后应该有235种可能。这肯定会超时,所以需要剪枝。

  剪枝的情况是:

  1、当前的发电站个数大于当前所需最少的发电站个数。这样已经没必要进行下去了,因为不可能产生更优的解。

  2、如果在某一点放发电站以后,通电的城市的个数没有增加,也不用再继续了。

  3、枚举第k点的时候,如果它前面的点(1 ~ k-1)存在不通电的城市x,并且后面的点(k ~ n)中不存在与x相邻的点,也不用再继续了。原因是x这个点(城市)怎么也不可能通电。它本身不能放发电站(枚举的就是它不放发电站的情况),其后面的点又不能为它供电。


下面是丑陋的代码:

图片 1图片 2

 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     else
20     {
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("%dn",Min);
80     }
81     return 0;
82 }

View Code

 

PS:感觉剪枝非常需要分析能力。脑袋不够用了。