记录编号	587571	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]关押罪犯	最终得分	100
用户昵称	宇战	是否通过	通过
代码语言	C++	运行时间	0.333 s
提交时间	2024-04-09 19:47:14	内存使用	12.60 MiB

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=2e5+10,M=2e5+10;
int head[M],ver[M],tot,Next[M],edge[M];
void add(int x,int y ,int z){
    ver[++tot]=y;
    edge[tot]=z;
    Next[tot]=head[x];
    head[x]=tot;
}
int cl[N];
struct node{
    int st,ed,zh;
}a[M];
bool cmp(node x,node y){
    return x.zh<y.zh;
}int v[N];
bool dfs(int x,int c){
    cl[x]=c;
    v[x]=1;
    for(int i=head[x];i;i=Next[i]){
        int y=ver[i];
        v[y]=1;
        if(cl[y]==0){
            if(!dfs(y,-c))return 0;
        }else if(cl[x]==cl[y]){
            return 0;
        }
    }
    return 1;
}

bool check(){
    memset(v,0,sizeof(v));
    for(int i=1;i<=n;i++){
        if(v[i]==0){
            if(dfs(i,1)==0){
                return false;
            }
        }
    }
    return true;
}
int ss=0;
int main(){
    freopen("prison1.in","r",stdin);
    freopen("prison1.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
       cin>>a[i].st>>a[i].ed>>a[i].zh;
    }
    sort(a+1,a+1+m,cmp);
    long long l=0,r=2e9+10;
    while(l<r){
        memset(cl,0,sizeof(cl));
        memset(head,0,sizeof(head));
        memset(ver,0,sizeof(ver));
        memset(edge,0,sizeof(edge));
        memset(Next,0,sizeof(Next));
        tot=0;
        int mid=l+r>>1;
        ss=m;
        for(int i=1;i<=m;i++){
                if(a[i].zh>mid){
                    break;
                }else{
                    ss=i;
                }
            }
            ss++;
        for(int i=ss;i<=m;i++){
            add(a[i].st,a[i].ed,a[i].zh);
            add(a[i].ed,a[i].st,a[i].zh);
        }
        if(check()){
            r=mid;
        }else{
            l=mid+1;
        }
    }
    cout<<l;
}