关押罪犯【C++】

此题显然是一道关于二分图的题目，因为数据较大，且属于最大值最小问题，所以很容易的可以联想到二分猜答案的方法来优化算法。

代码如下：

#include
#include
#include
#include
#define maxn 20005
using namespace std;
int color[maxn],n,m;
struct edge{
int u,v,w;
};
vectore;
vectorg[maxn],w[maxn];
bool BFS(int s,int c){
queueq;
q.push(s);
color[s]=1;
while(!q.empty()){
int i=q.front();q.pop();
int sz=g[i].size();
for(int k=0;k<sz;k++){
int j=g[i][k];
if(w[i][k]<=c)continue;
if(color[i]==color[j])return false;
if(color[j]==0){
q.push(j);
color[j]=3-color[i];
}
}
}
return true;
}
bool check(int c){
memset(color,0,sizeof(color));
bool ok=true;
for(int i=1;i<n;i++)
if(color[i]==0){
ok=BFS(i,c);
if(!ok)return false;
}
return true;
}
int main(){
scanf("%d%d",&n,&m);
int x,y,z;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
g[x].push_back(y);
g[y].push_back(x);
w[x].push_back(z);
w[y].push_back(z);
}
int A=0,B=350000,ans=0; //范围有进行过优化
while(A<=B){
int c=(A+B)/2;
if(check(c))B=c-1,ans=c;
else A=c+1;
}
printf("%d",ans);
return 0;
}

！！！注意：

bool check(int c){
memset(color,0,sizeof(color));
bool ok=true;
for(int i=1;i<n;i++)
if(color[i]==0){
ok=BFS(i,c);
if(!ok)return false;
}
return true;
}

bool BFS(int s,int c){
queueq;
q.push(s);
color[s]=1;
while(!q.empty()){
int i=q.front();q.pop();
int sz=g[i].size();
for(int k=0;k<sz;k++){
int j=g[i][k];
if(w[i][k]<=c)continue;
if(color[i]==color[j])return false;
if(color[j]==0){
q.push(j);
color[j]=3-color[i];
}
}
}
return true;
}

这段代码是本题解答的重点：判定是否为二分图，切记要将数组color清零。