本文共 3675 字，大约阅读时间需要 12 分钟。

这个是可以用二分+二分图验证来做的

不过数据丧心病狂 有时候会有边权相同的时候 sort排序后发现 位置变了。。。答案错了

如果反向边加到a+n里 sort 60分

如果反向边加到a+1里 sort 70分

反向边加到a+1里 stable_sort  AC

这个错误改了好长时间。。。。丧心病狂

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int lim=100020;int m,n;struct self{int x,y,w;}s[lim*2];int first[lim*2],nxt[lim*2];int a,b,c;int l,r,mid,ans;int cmp(self a1,self a2){return a1.w>a2.w;};int col[lim];bool dfs(int i,int c){    if(col[i]!=-1)    {        if(col[i]==c)return false;        return true;    }    col[i]=1-c;    for(int e=first[i];e!=-1;e=nxt[e])    if(e<=mid)    if(!dfs(s[e].y,1-c))return false;    return true;}bool ok(){    int a;    bool p=1;    memset(col,-1,sizeof(col));    for(a=1;a<=m;a++)    if(col[a]==-1)    {        p=dfs(a,1);        if(!p)return p;    }    return p;}    int main(){    memset(first,-1,sizeof(first));    memset(nxt,-1,sizeof(nxt));    scanf("%d%d",&m,&n);    for(a=1;a<=2*n;a+=2)    {        scanf("%d%d%d",&s[a].x,&s[a].y,&s[a].w);        s[a+1].y=s[a].x;s[a+1].x=s[a].y;s[a+1].w=s[a].w;    }    stable_sort(s+1,s+n+n+1,cmp);    for(a=1;a<=2*n;a++)    {        nxt[a]=first[s[a].x];        first[s[a].x]=a;    }    l=1;r=n;ans=0;    while(l<=r)    {        mid=(l+r)>>1;        mid*=2;        memset(col,-1,sizeof(col));        if(ok())        l=mid/2+1;        else        {            r=mid/2-1;            ans=s[mid].w;        }    }    cout<
       
        <
       
      
     
    
   

另外还有并查集的做法

并查集又有很多种 还是写那个带rank的吧

突然发现并查集也不会写了！！！！！！尼玛这是要考NOIP的节奏吗？！！！

写错了三个地方

1.find函数里  一定要先设置一个x 表示x原来的父亲

    rank原来是i和x的关系 所以一定要记录x 然后再由rank x 更新rank i 

2..当l!=r时 合并 不能简单地 rank[l]=(rank[r]+1)%2;

    因为x和y不在一个集合中 此时l和r不一定不在一个集合

    比如 rank[x]=1  rank[y]=0时  x就该和y在一个集合中 这样才能保证x和y不在一个集合！！！

3.当l==r时

   判断rank[x]和rank[y]

   因为l==r  表示x和y的父亲是同样的

   rank[i]表示i到父亲的距离，即i是否和父亲关在一个监狱中

   当rank[x]==rank[y]时 x和y关到了一个监狱中 不符合要求了

带权并查集 一定要耐心细心！！！不能想当然！！！

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int lim=100020;int m,n;struct self{int x,y,w;}s[lim*2];int first[lim*2],nxt[lim*2];int a,b,c;int f[lim],rank[lim];int l,r;int cmp(self a1,self a2){return a1.w>a2.w;};int find(int i){    if(f[i]==i)return i;    int x=f[i];    f[i]=find(x);    rank[i]=(rank[x]+rank[i])%2;    return f[i];}int main(){    memset(first,-1,sizeof(first));    memset(nxt,-1,sizeof(nxt));    scanf("%d%d",&m,&n);    for(a=1;a<=m;a++)f[a]=a;    for(a=1;a<=2*n;a+=2)scanf("%d%d%d",&s[a].x,&s[a].y,&s[a].w);    sort(s+1,s+n+n+1,cmp);    for(a=1;a<=n;a++)    {        l=find(s[a].x);r=find(s[a].y);        if(l!=r)        {            f[l]=r;            if(rank[s[a].x]==rank[s[a].y])           //不能直接rank[l]=(rank[r]+1)%2;            rank[l]=1;else rank[l]=0;        }        else        if(rank[s[a].x]==rank[s[a].y])        {            cout<
       
        <
       
      
     
    
   

转载地址：https://blog.csdn.net/li412302070/article/details/14132433 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！