1015-Dominating Set
英文読解が大変。
英語版Wikipediaに助けられました。
dfsで全探索する。
計算量はO(2^y)
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int MAX_V=30; int V; char g[MAX_V][MAX_V]; int memo[MAX_V]; int a,b,y; int ans; void dfs(int used,int covered,int now,int k){ if(ans<=now)return; if(covered==(1<<V)-1){ ans=min(ans,now);return; } int t; for(int i=k;i<V;i++){ if((used&(1<<i))==0){ t=covered; t|=memo[i]; dfs(used|(1<<i),t|(1<<i),now+1,i+1); } } } int main() { for(;;){ cin >> V >> y;if(V==0&&y==0)break; memset(g,0,sizeof(g)); if(V>MAX_V)return -1; for(int i=0;i<y;i++){ cin >> a >> b; g[a][b]=1;g[b][a]=1; } for(int i=0;i<V;i++){ int t=0; for(int j=0;j<V;j++){ if(g[i][j]==1){ t|=1<<j; } } memo[i]=t; } ans=9999; dfs(0,0,0,0); cout << ans << endl; } return 0; }