欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷 P1525 关押罪犯(二分 + 二分图判定)

程序员文章站 2022-07-05 18:32:12
...

洛谷 P1525 关押罪犯(二分 + 二分图判定)
思路:
脑子不是很清醒。。。
有两个*关这些犯人,然后如果两个有矛盾的范围关在同一个*就会产生影响cic_i,现在让你输出最大影响的最小值是是多少。
我们二分答案:最大影响值dd,也就是说大于这个最大值的犯人肯定会被关在两个不同的*,我们在大于dd的两个犯人之间连一条边,这两个犯人肯定会属于不同的两个*(点集),如果dd可行,那么肯定会形成一个二分图,所以我们用染色法判断是否为二分图从而判断方案是否可行。

struct Edge{
    int next;
    int to;
    int dis;
}edge[N<<1];
int head[N<<1],tot;
inline void add(int from,int to,int dis){
    edge[++tot].next = head[from];
    edge[tot].to = to;
    edge[tot].dis = dis;
    head[from] = tot;
}
int color[N];
bool dfs(int x,int d){
    bool r = 1;
    for(int i = head[x];i;i = edge[i].next){
        int y = edge[i].to;
        int dis = edge[i].dis;
        if(dis > d){
            if(color[y] == 0) {color[y]=color[x]==1?2:1;r = dfs(y,d);if(r==0) return false;}
            else if(color[y] == color[x]) return false;
        }
    }
    return true;
}
bool ok(int m,int n){
    memset(color,0,sizeof color);
    rep(i,1,n){
        if(!color[i]) {
            color[i] = 1;
            bool r = dfs(i,m);
            if(r == 0) return false;
        }
    }
    return true;
}
int main(){
    int l(0),r(0);
    int n = read(),m = read();
    rep(i,1,m){
        int u = read(),v = read(),d = read();
        add(u,v,d);
        add(v,u,d);
        r = max(r,d);
    }
    while(l < r){
        int mid = l + r >> 1;
        if(ok(mid,n)) r = mid;
        else l = mid + 1;
    }
    cout << r;
}