P1525 [NOIP2010 提高组] 关押罪犯

description

描述
S城现有两座监狱，一共关押着N名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。
很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。
我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。
如果两名怨气值为c的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为c的冲突事件。
每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到S城Z市长那里。
公务繁忙的Z市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。
在详细考察了N名罪犯间的矛盾关系后，警察局长觉得压力巨大。
他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。
假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。
那么，应如何分配罪犯，才能使Z市长看到的那个冲突事件的影响力最小？这个最小值是多少？

格式
输入格式
输入文件的每行中两个数之间用一个空格隔开。

第一行为两个正整数N和M，分别表示罪犯的数目以及存在仇恨的罪犯对数。

接下来的M行每行为三个正整数aj，bj，cj，表示aj号和bj号罪犯之间存在仇恨，其怨气值为cj。

数据保证1<=aj<=bj<=N,0<=cj<=1000000000,且每对罪犯组合只出现一次。

输出格式
输出文件共1行，为Z市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出0。

样例输入
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
样例输出
3512
提示
分配方法：市长看到的冲突事件影响力是3512（由2号和3号罪犯引发）。其他任何分法都不会比这个分法更优。
对于30%的数据有N≤15。
对于70%的数据有N≤2000，M≤50000。
对于100%的数据有N≤20000，M≤100000。

solution

题目里面说了 :

按影响力从大到小排成一个列表

所以不妨我们就按照它说的来做。

那么从大到小处理，如果能够通过“分配到两个不同的监狱”来避免这个冲突的发生，那么我们就分。

反之如果没有办法分到两个不同的监狱，我们就输出（因为从大到小之后第一个矛盾的情况一定是答案，你后面不管怎么决策都不会影响答案了）。

然后你会发现这里对于一个罪犯和其他罪犯之间的关系是可能有多条的。

所以我们就需要用到并查集来维护这些不同的信息。

考虑怎么样把两个罪犯分到不同监狱之后维护他们之间的位置（在哪个监狱）信息。

第一个想法是建立两个集合 \(A,B\) 来表示 A和B 两个监狱。

但是这样做的话有可能一个人会被同时分到两个监狱里去，非常不好处理。

怎么办？既然这里是会出现“一个人在两个监狱里面”。

那么我们就把这个情况变得好处理一些。

对于任意的一个罪犯 \(x\) ，我们考虑建立一个他的在另一个监狱的镜像 \(x^{'}\)。

这个 \(x^{'}\) 有什么用呢？

如果说 \(x ,y\)不能够相连（关在一起），那么我们就把 \(y\) 和 \(x^{'}\) 合并。

意味着 \(x\) 和 \(y\) 不在同一个监狱（因为 \(x^{'}\) 就代表\(x\)在另一个监狱的“镜像”，而镜像和本体是不在一起的）

那么信息就得到了维护。

考虑什么时候矛盾。

很明显，假设新扫到的二元组 \((x,y)\) 已经因为前面的关系而关在一起了。

那么矛盾必定发生，输出即可。

代码：


#include
using namespace std;

const int si_n=2e4+10;
const int si_m=1e5+10;

int pa[si_n*2];
#define mir(x) x+n // the mirror of element 'x'

struct node{
    int u,v,w;
    bool operator < (const node &b)const{
        return w>b.w;
    }
}e[si_m];

int root(int x){
    if(pa[x]!=x){
        return pa[x]=root(pa[x]);
    }
    return pa[x];
}

void Union(int x,int y){
    int rx=root(x),ry=root(y);
    if(rx==ry) return;
    pa[rx]=ry;
}

bool query(int x,int y){
    if(root(x)==root(y)) return true;
    return false;
}

int n,m;

int main(){
    cin>>n>>m;
    for(register int i=1;i<=m;++i){
        cin>>e[i].u>>e[i].v>>e[i].w;
    }
    for(register int i=1;i<=n*2;++i){
        pa[i]=i;
    }
    sort(e+1,e+1+m);
    for(register int i=1;i<=m;++i){
        int x=e[i].u,y=e[i].v,w=e[i].w;
        if(query(x,y)==true){
            return printf("%d\n",w),0;
        }
        else{
            Union(x,mir(y));
            Union(y,mir(x));
        }
    }
    return printf("0"),0;
}

Algor-并查集 Cate-数据结构 Type-题解

P1525 [NOIP2010 提高组] 关押罪犯

description

solution

相关

标签