Luogu

分析

二分答案,问题变为是否存在一种方案使得任意一对怨气值 $>mid$ 的罪犯不在一个监狱里。

我们把所有怨气值 $>mid$ 的罪犯拿出来连边,然后判断图是否为二分图即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=20000+10,M=100000+10;

int n,m;

struct sedge { int u,v,w; } se[M];
struct edge { int v,nxt; } e[M<<1];
int head[N],ecnt=0;
inline void addEdge(int u,int v) {
    e[++ecnt]=(edge){v,head[u]},head[u]=ecnt;
}

int vis[N],col[N],flag;
inline void dfs(int u,int c) {
    vis[u]=1,col[u]=c;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (vis[v]) {
            if (col[u]==col[v]) { flag=1; return; }
            continue;
        }
        dfs(v,c^1); if (flag) return;
    }
}
inline int check(int mid) {
    memset(head,0,sizeof(head)),ecnt=0;
    memset(vis,0,sizeof(vis)),flag=0;
    for (re int i=1;i<=m;++i)
        if (se[i].w>mid) {
            addEdge(se[i].u,se[i].v);
            addEdge(se[i].v,se[i].u);
        }
    for (re int i=1;i<=n;++i)
        if (!vis[i]) { dfs(i,0); if (flag) return 0; }
    return 1;
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i) se[i]=(sedge){read(),read(),read()};
    int L=0,R=1e9;
    while (L<R) {
        int mid=(L+R)>>1;
        if (check(mid)) R=mid;
        else L=mid+1;
    }
    printf("%d\n",L);
    return 0;
}
最后修改:2019 年 10 月 28 日 10 : 46 AM