题意：给一个有n个点m条边的无向图，染色某些点，使得任意一条边都有某个端点被染色，其实就是求最小点覆盖的点数。
(2<=n<=500,1 < m< n*(n-1)/2) 有个特殊的条件就是对于任意一条边e(u,v) min(u,v)<=30
比赛的时候没做出来。。考虑这题的时候注意到那个特殊条件，想到过枚举，但是只想到2^30那种二进制枚举肯定不行。。然后没有反应过来用搜索做。。
这题正解应该是dfs+剪枝
参考了这个blog:http://blog.csdn.net/u012127882/article/details/46547571
做法是枚举前30个点的情况，先依次枚举每一个点，然后判定这个点之前的点是否都能互相覆盖，然后再评估一下当前情况需要多少个点才能覆盖掉与之前点相连的边。二进制压缩状态，可以用位运算。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=510;
const int MAXM=MAXN*MAXN;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
struct Edge {
int to,next;
Edge(){}
Edge(int _to,int _next):to(_to),next(_next){}
}e[MAXM];
int head[MAXN],tot,n,m;
void init(){
memset(head,-1,sizeof(head));
tot=0;
}
void AddEdge(int u,int v){
e[tot]=Edge(v,head[u]);
head[u]=tot++;
e[tot]=Edge(u,head[v]);
head[v]=tot++;
}
int fg[MAXN],res[MAXN];
void build(int u){
res[u]=fg[u]=0;
for(int i=head[u];~i;i=e[i].next){
int to=e[i].to;
if(to<30)fg[u]|=(1<<to);
else res[u]++;
}
}
bool ok(int u,int flag){
for(int i=u;i<30;i++)flag|=(1<<i);
for(int i=0;i<30;i++){
if(!(flag&(1<<i))&&(fg[i]&flag)!=fg[i])
return 0;
}
return 1;
}
int solve(int flag){
int cnt=0;
for(int i=30;i<n;i++){
if((fg[i]&flag)!=fg[i])++cnt;
}
return cnt;
}
int ans;
void dfs(int u,int flag,int cnt){
if(!ok(u,flag))return ;
int tmp=flag;
for(int i=u;i<30&&i<n;i++) tmp|=(1<<i);
if(cnt+solve(tmp)>=ans)return ;
if(u>=n||u>=30){
ans=min(ans,cnt+solve(flag));
return ;
}
if(((flag&fg[u])==fg[u])&&!res[u]){
dfs(u+1,flag,cnt);
return ;
}
dfs(u+1,flag,cnt);
dfs(u+1,flag|(1<<u),cnt+1);
}
int main()
{
while(~scanf("%d%d",&n,&m)){
init();
for(int i=0,x,y;i<m;i++){
scanf("%d%d",&x,&y);
--x;--y;
AddEdge(x,y);
}
for(int i=0;i<n;i++)build(i);
ans=30;
dfs(0,0,0);
printf("%d\n",ans);
}
return 0;
}
|
