题解：P1525 [NOIP2010 提高组] 关押罪犯

题解：P1525 [NOIP2010 提高组] 关押罪犯

题意：对于一个图，把点分成两个集合，删去跨集合的边后让最大边权最小。
看到这里可以明显的想到二分图。

二分图

定义：
二分图，又称二部图，英文名叫 Bipartite graph。指节点由两个集合组成，且两个集合内部没有边的图。

观察发现，与本题的要求刚好相反，那么自然可以想到：

• 设答案为 ans。
• 对于边权小于 ans 的边在同一个集合内，则在二分图中可以不考虑。
• 只考虑边权大于 ans 的边，则图一定是一个二分图。

现在我们知道，要判断一个答案是否合法，只要把大于答案的边连起来，判断是否为一个二分图。
介绍一个 dfs 判断二分图的方法：

bool dfs(LL v, LL c){
    color[v] = c;    //将当前顶点涂色
    for(int i = 0; i < n; i++){    //遍历所有相邻顶点，即连着的点
        if(edge[v][i] == 1){    //如果顶点存在
            if(color[i] == c)    //如果颜色重复，就返回false
                return false;
            if(color[i] == 0 && !dfs(i,-c))    //如果还未涂色，就染上相反的颜色-c,并dfs这个顶点，进入下一层
                return false;   //返回false
        }
    }
    return true;   //如果所有顶点涂完色，并且没有出现同色的相邻顶点，就返回true
}

至于答案的话，采用二分答案的方法：

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>e[i].x>>e[i].y>>e[i].w;//按边存，方便排序
    }
    sort(e+1,e+m+1);
    LL l=0,r=m,mid;
    while(l<r-1){
        mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid;
    }
    if(m==1) cout<<0;//特判
    else cout<<e[r].w;
    return 0;
}

代码

怕大家看不懂，参考了 @FY0123 大佬的代码重写了一遍，自己的码风不太好。

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
LL n,m,col[500005];
bool flag;
struct node{
    LL x,y,w;
    bool operator < (const node &p)const{
        return p.w>w;
    }
}e[500005];
vector<LL> v[500005];
void dfs(LL x,LL c){
    col[x]=c;
    for(auto i : v[x]){
        if(!col[i]) dfs(i,c^1);
        else if(col[i]==c) flag=0;
    }
}
bool check(LL x){
    for(int i=1;i<=n;i++) v[i].clear();
    memset(col,0,sizeof(col));flag=1;
    for(int i=x+1;i<=m;i++){
        v[e[i].x].emplace_back(e[i].y);
        v[e[i].y].emplace_back(e[i].x);
    }
    for(int i=1;i<=n;i++){
        if(!col[i]){
            dfs(i,0);
            if(!flag) return 0;
        }
    }
    return 1;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>e[i].x>>e[i].y>>e[i].w;
    }
    sort(e+1,e+m+1);;
    LL l=0,r=m,mid;
    while(l<r-1){
        mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid;
    }
    if(m==1) cout<<0;//特判
    else cout<<e[r].w;
    return 0;
}