题解 P1525 【关押罪犯】

总体来讲这是一个并查集的题,我们把模型抽象出来,就是一张无向图,要求按照条件将图中的点分成两部分,使得两个集合中的最大边最小

仔细想想,这是一道基于并查集的题,而且一定会把大的边割断使这条边不存在,只是一个小贪心,但是普通的并查集思想又不是很好做,所以我们有了以下分析:

既然是贪心,我们会根据边的大小来排序,由大到小排;

假设当前点线是A—B,则有以下几种情况:

<1> A,B都分别还没有在任何一个监狱中,所以我们这时候把A,B分别放入两个对立的监狱,至于对立的监狱的概念,我们为了方便代码实现,就定义任意一个监狱编号为X,则X^1为监狱X的对立监狱;

<2>A,B中有一个人A已经在监狱中了,而另一个人B没有,则我们把B放入A所在监狱的对立监狱;

<3>A,B都在监狱中,但两所监狱不是对立的,我们把A放在B目前的监狱的对立监狱,此时A的监狱编号已经改变,我们把原A所在的监狱的对立监狱的人放在现在B所在的监狱;

<4>A,B都在监狱中,且所在监狱相同,则这条边就是答案;

放监狱这个步骤就是并查集,排序是贪心,所以这道题是贪心+并查集;

我的博客: http://blog.csdn.net/pretend\_fal

完整代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#define II int
#define R register
#define I 123456
using namespace std;

struct node {
    II x,y;
    II w;
}aa[I];

II fa[I];

II n,m,ans,_tot;

bool maP(node a1,node a2)
{
    return a1.w>a2.w;
}

II find(R II x)
{
    if(fa[x]==x) return x;
      else return fa[x]=find(fa[x]);
}

int main()
{
    scanf("%d%d",&n,&m);
    _tot=22001;
    //监狱编号在>n时认为已经放到监狱中了
    //所以,为了避免与初始状态重复,我们令最小的监狱编号为n范围之外
    for(R II i=1;i<=40000;i++) fa[i]=i;
    for(R II i=1;i<=m;i++) scanf("%d%d%d",&aa[i].x,&aa[i].y,&aa[i].w);
    sort(aa+1,aa+m+1,maP);
    ans=0;
    for(R II i=1;i<=m;i++)
    {
        R II X=find(aa[i].x);
        R II Y=find(aa[i].y);
        if(X<=n&&Y<=n) fa[X]=++_tot,fa[Y]=++_tot;
        //情况<1>;
          else if(X<=n&&Y>n) fa[X]=fa[Y]^1;
          //情况<2>之一;
            else if(X>n&&Y<=n) fa[Y]=fa[X]^1;
            //情况<2>之二;
              else if(X>n&&Y>n){
                  if(X==Y) {
                      printf("%d\n",aa[i].w);
                      return 0;
                  }
                  //情况<4>;
                  if(X!=(Y^1)){
                      R II XXOR=X^1;
                      R II YXOR=Y^1;
                      fa[Y]=XXOR;
                      fa[YXOR]=X;
                  }
                  //情况<3>;
              }
    }
    cout<<0<<endl;
    return 0;
}

发表于 2017-09-23 07:04:20 in 题解