算是很裸的吧，二分半徑，然后2-sat判定能不能滿足條件。

#include <bits/stdc++.h> using namespace std; const int maxn=1222; const double eps=1e-9; struct node{double x,y; }p[maxn]; struct twoset{int n;vector<int>g[maxn<<1];bool mark[maxn<<1];int s[maxn<<1],c;bool dfs(int x){if(mark[x^1])return false;if(mark[x])return true;mark[x]=true;s[c++]=x;for(int i=0;i<g[x].size();i++)if(!dfs(g[x][i]))return false;return true;}void init(int n){this->n=n;for(int i=0;i<n*2;i++)g[i].clear();memset(mark,0,sizeof mark);}void add_clause(int x,int xval,int y,int yval){x=x*2+xval;y=y*2+yval;g[x^1].push_back(y);g[y^1].push_back(x);}bool solve(){for(int i=0;i<n*2;i+=2){if(!mark[i]&&!mark[i+1]){c=0;if(!dfs(i)){while(c>0)mark[s[--c]]=false;if(!dfs(i+1))return false;}}}return true;} }solver;double getdis(node a,node b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } void run(int n){for(int i=0;i<n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);double l=0,r=30000,ans=0;while(l+eps<=r){double mid=(l+r)/2;solver.init(n);for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){double dis=getdis(p[i],p[j]);if(dis<2*mid){solver.add_clause(i,0,j,0);solver.add_clause(i,1,j,1);}}if(solver.solve())ans=mid,l=mid+eps;else r=mid-eps;}solver.init(n);for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){double dis=getdis(p[i],p[j]);if(dis<2*ans){solver.add_clause(i,0,j,0);solver.add_clause(i,1,j,1);}}solver.solve();printf("%.8lf\n",ans);for(int i=0;i<n;i++){if(solver.mark[i<<1])putchar('1');else putchar('2');printf("%c",i==n-1?'\n':' ');} } int main() { // freopen("in","r",stdin);int n;while(scanf("%d",&n)>0)run(n);return 0; }

　　

轉載于:https://www.cnblogs.com/wshh/p/4029828.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的ZOJ3370. Radio Waves(2-sat)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。