PKU 1620 Phone Home

http://poj.org/problem?id=1620
グラフの彩色問題のようなやつ。

枝刈り全探索しました。

pair<double,double> in[12];
vector<int> G[12];
int vis[12];
int n;

bool dfs(int v,int ki){
  if(v==n)return true;
    
  rep(i,ki){
    vis[v]=i;
    bool ok=true;
    FOR(it,G[v]){
      if(*it<v && vis[*it]==i){
        ok=false;
        break;
      }
    }
    if(ok && dfs(v+1,ki))return true;
  }

  return false;
}

main(){
  int ca=0;
  while(cin>>n,n){
    ++ca;
    rep(i,n)G[i].clear();
    memset(vis,0,sizeof(vis));
    

    rep(i,n){
      cin>>in[i].F>>in[i].S;
      rep(j,i){
        double tx=in[i].F-in[j].F,ty=in[i].S-in[j].S;
        if(tx*tx+ty*ty<=20*20){
          G[i].pb(j);
          G[j].pb(i);
        }
      }
    }
    int ans=5;
    rep(i,4){
      if(dfs(0,i+1)){
        ans=i+1;
        break;
      }
    }
    cout<<"The towers in case "<<ca<<" can be covered in "<<ans<<" frequencies."<<endl;
  }
}