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; } }