关键词：并查集，二分图，树剖，树上差分，LCA，搜索。
例题一：
CodeForces-85E：Guard Towers
题意：给定平面上N个点(N<=5000)，以及N个点的坐标。现在可以把每个点染成红色或者蓝色。求最小化同色点的最大距离，且求出相应的方案数。
思路：二分答案L，把距离大于等于L的连边，然后判定是否是二分图： 对于求方案数，ans=pow(2,cnt)，cnt是连通块的数量。因为每个连通块是二分图，一个二分图的染色方案只有两种。 复杂度O(N^2*logL)。
（当然，最优的解法是转化为切比雪夫距离，复杂度低很多，这里先不管它。）
#include<cstdio> #include<vector> #include<cstdlib> #include<iostream> #include<algorithm> using namespace std; const int maxn=5010; const int Mod=1e9+7; vector<int>G[maxn]; int x[maxn],y[maxn],vis[maxn],col[maxn],N; int qpow(int a,int x){ int res=1; while(x){ if(x&1) res=(res*1ll*a)%Mod; x>>=1; a=(a*1ll*a)%Mod; } return res; } void read(int &res){ char c=getchar();res=0; for(;c<'0'||c>'9';c=getchar()); for(;c>='0'&&c<='9';c=getchar()) res=(res<<3)+(res<<1)+c-'0'; } void init(int len){ for(int i=1;i<=N;i++) vis[i]=0,G[i].clear(); for(int i=1;i<=N;i++) for(int j=i+1;j<=N;j++){ int dis=abs(x[i]-x[j])+abs(y[i]-y[j]); if(dis>len) { G[i].push_back(j); G[j].push_back(i); } } } bool dfs(int u,int opt) { vis[u]=1; col[u]=opt; int L=G[u].size(); for(int i=0;i<L;i++){ int v=G[u][i]; if(!vis[v]) { if(!dfs(v,opt^1)) return false; } else if(col[v]==opt) return false; } return true; } bool check(int len) { init(len); for(int i=1;i<=N;i++){ if(!vis[i]) { if(!dfs(i,0)) return false; } } return true; } int main() { read(N); for(int i=1;i<=N;i++) read(x[i]),read(y[i]); int L=0,R=10000,Mid,ans; while(L<=R){ Mid=(L+R)>>1; if(check(Mid)) ans=Mid,R=Mid-1; else L=Mid+1; } init(ans); int cnt=0,ans2; for(int i=1;i<=N;i++){ if(!vis[i]){ cnt++; dfs(i,0); } } ans2=qpow(2,cnt); printf("%d %d ",ans,ans2); return 0; }
#include<cstdio> #include<vector> #include<cstdlib> #include<iostream> #include<algorithm> using namespace std; const int maxn=5010; const int Mod=1e9+7; int x[maxn],y[maxn],vis[maxn],col[maxn],N; int qpow(int a,int x){ int res=1; while(x){ if(x&1) res=(res*1ll*a)%Mod; x>>=1; a=(a*1ll*a)%Mod; } return res; } void read(int &res){ char c=getchar();res=0; for(;c<'0'||c>'9';c=getchar()); for(;c>='0'&&c<='9';c=getchar()) res=(res<<3)+(res<<1)+c-'0'; } bool dfs(int u,int opt,int len) { vis[u]=1; col[u]=opt; for(int v=1;v<=N;v++){ if(abs(x[u]-x[v])+abs(y[u]-y[v])<=len) continue; if(!vis[v]) { if(!dfs(v,opt^1,len)) return false; } else if(col[v]==opt) return false; } return true; } bool check(int len) { for(int i=1;i<=N;i++) vis[i]=0; for(int i=1;i<=N;i++){ if(!vis[i]) { if(!dfs(i,0,len)) return false; } } return true; } int main() { read(N); for(int i=1;i<=N;i++) read(x[i]),read(y[i]); int L=0,R=10000,Mid,ans; while(L<=R){ Mid=(L+R)>>1; if(check(Mid)) ans=Mid,R=Mid-1; else L=Mid+1; } int cnt=0,ans2; for(int i=1;i<=N;i++) vis[i]=0; for(int i=1;i<=N;i++){ if(!vis[i]){ cnt++; dfs(i,0,ans); } } ans2=qpow(2,cnt); printf("%d %d ",ans,ans2); return 0; }
例题二：
CodeForces-164D：Minimum Diameter
题意：给定平面上N个点(N<=1000)，以及N个点的坐标。给定K，求删去K个点后，最小化的最远距离。
思路：同上，二分答案，把大于等于L的连边，然后就是求最小点覆盖，即每条边至少有一个点被覆盖(删去)。但是没有规律的无向图的最小点覆盖是NP问题，只能暴力，这里小小的优化一下，如果一个点的入度是1，那么显然覆盖那边边的另一个点。
如果没有见过，两个代码都不是那么好实现（特别是第二个，哭晕）。
例题三：
CodeForces-19E：Fiary
题意：给定N点M边的无向图，问删去一条边后变为二分图的情况有哪些。
思路：和上面两题有些不一样，不是二分+判定题。 如果存在奇环，则不是二分图。然后（blabla，总之）需要删去的边为所有奇环所共有，且不在偶环上。
具体实现：DFS出一棵生成树，然后染色。对于剩下的没有参与生成树的边，如果两端同色，表示形成了奇环，则在奇环上每条边+1，否则在偶环上-1，最后边权对于奇环总数的边则为答案边。 +1和-1操作可以通过LCA+差分或者树剖实现。