AOJ : 1015 - Dominating Set
問題概要
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1015
NP困難として知られている問題らしいです.
詳しくは, 次のページを参照してください.
http://ja.wikipedia.org/wiki/%E6%94%AF%E9%85%8D%E9%9B%86%E5%90%88%E5%95%8F%E9%A1%8C
プログラム
#include <stdio.h> #include <string.h> #define MAX 30 #define REP(i,n,m) for(i=n;i<m;i++) #define rep(i,n) REP(i,0,n) int ans,x,y; int t[MAX][MAX],size[MAX]; int flg[MAX]; int isDomSet(void){ int i,j; rep(i,x){ if(!flg[i]){ rep(j,size[i]) if(flg[t[i][j]]) break; if(j == size[i]) return 0; } } return 1; } void solve(int idx,int cost){ if(idx == x){ if(ans > cost && isDomSet()) ans = cost; return; } flg[idx] = 0; solve(idx+1,cost); flg[idx] = 1; solve(idx+1,cost+1); } int main(void){ int i,from,to; while(scanf("%d%d",&x,&y) && (x||y)){ memset(t,0,sizeof(t)); memset(size,0,sizeof(size)); rep(i,y){ scanf("%d%d",&from,&to); t[from][size[from]++] = to; t[to][size[to]++]= from; } ans = x; solve(0,0); printf("%d\n",ans); } return 0; }