当然是二分. 然后连一个图, 染色判断是不是二分图即可. 方案数就是 2^(连通块个数).
别真的连边! 不然时间空间都会爆.
别预处理 dis ! 要现算. 不然会 T.
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<cmath>
- #define ll long long
- using namespace std;
- const int N=5005;const ll mod=1e9+7;
- int n,x[N],y[N],l,r,ans;
- int hd[N],xnt,prn,mid;
- bool vis[N],col[N];
- int calc(int i,int j)// 别预处理 dis!!!
- {
- return abs(x[i]-x[j])+abs(y[i]-y[j]);
- }
- bool dfs(int cr)
- {
- vis[cr]=1;
- for(int i=1;i<=n;i++)
- if(i!=cr&&calc(i,cr)>mid)
- {
- if(!vis[i])
- {
- col[i]=!col[cr];
- if(dfs(i))return true;
- }
- else if(col[i]==col[cr])return true;
- }
- return false;
- }
- bool check()
- {
- memset(vis,0,sizeof vis);// 不 memset col!
- for(int i=1;i<=n;i++)
- if(!vis[i])
- if(dfs(i))return false;
- return true;
- }
- void dfsx(int cr)
- {
- vis[cr]=1;
- for(int i=1;i<=n;i++)
- if(!vis[i]&&calc(i,cr)>ans)
- dfsx(i);
- }
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- scanf("%d%d",&x[i],&y[i]);
- r=10000;//
- while(l<=r)
- {
- mid=((l+r)>>1);
- if(check())ans=mid,r=mid-1;
- else l=mid+1;
- }
- memset(vis,0,sizeof vis);prn=1;
- for(int i=1;i<=n;i++)if(!vis[i])prn=((ll)prn<<1)%mod,dfsx(i);
- printf("%d\n%d",ans,prn);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2676951.html