Description
每年的CQOI比赛结束后都会组织选手参加一次游玩活动。由于人数众多，通常会把选手分成两队出发。组委会为了和谐，想尽量把比较熟悉的选手分在同一队。我们用“友好度”（一个正整数值）来表示某两位选手之间的熟悉程度，友好度越大，则两名选手越熟悉。而“和谐度”定义为两队中熟悉程度最低的那对选手的友好度。
现在告诉你选手数量和一些选手之间的友好度，该如何分队(每组至少1人)，才能让两队的和谐度达到最大。请你来帮助组委会完成这个任务。
Input
第一行为两个正整数n，分别选手的数目以及友好度大于0的选手对数，选手编号为1~n。，选手编号为1~n。
接下来是一个n*n的矩阵，矩阵的第i行第j列表示选手i和选手j的友好度c，当i==j时c=0，注意，矩阵一定是斜对称的。
Output
一个整数，表示最大和谐度，某些情况下可能为0。
Hint
2<=n<=1000
Solution
首先这道题是一道需要二分猜答案的二分图练习题。需要求的是最大和谐度，也就是最小友好度，那么就用邻接矩阵存每一段友好度（也就是每一条边的权值），dfs的时候将大于猜的那个答案的值的边跳过，小于这个值的边染色为1和2，判断小于这个答案的所有边是否能构成二分图。然后因为这个图不一定连通所以当vis等于0的时候就需要dfs一次。
定义一个L和R，把L赋初值为0，R赋初值为midx，当mid满足条件时就往右边猜，往右边猜就要把L更新成mid+1，否则就往左边猜，把R更新成mid-1，最后当L=R的时候while循环退出输出ans，程序结束。 注意事项： 1.g[s][q]>=mid和s==q的时候都需要跳过，只有到遇到vis的值为1且两个端点颜色相等的时候就return false,或者它的子图不连通的时候return false。 2.每一次check(mid)之前要把color数组和vis数组清零避免爆了（。） 3.猜答案的时候跳L和R要+1和-1
#include#include #include #include #define maxn 1005using namespace std;int n,midx,midn,ans;bool flag;int g[maxn][maxn],color[maxn];bool vis[maxn];void init(){ scanf("%d",&n); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ scanf("%d",&g[i][j]); } }}bool dfs(int s,int c,int mid){ color[s]=c; vis[s]=true; for(int q=1;q<=n;q++){ if(g[s][q]>=mid)continue; if(s==q)continue; if(vis[q]){ if(color[s]==color[q])return false; } else if(dfs(q,3-c,mid)==false)return false; } return true;}void tomid(){ for(int q=1;q<=n;q++){ for(int p=1;p<=n;p++){ midx=max(midx,g[q][p]); } } midn=0;}bool check(int mid){ memset(color,0,sizeof(color)); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) if(!vis[i]) if(!dfs(i,1,mid)) return false; return true;}int main(){ init(); tomid(); int mid=(midx+midn)/2; int L=0,R=midx; while(L<=R){ mid=(L+R)>>1; if(check(mid)){ ans=mid; L=mid+1; } else R=mid-1; } printf("%d\n",ans); return 0;}