题解 P1525 【关押罪犯】

· · 题解

蒟蒻看到这题其实思考了一些问题才开始编程，这里讲一下问题并且放出代码

为什么贪心是正确的

首先看到这道题大家都会想到把冲突值从大到小排序，然后从大到下进行加边，为什么之后加入的不会影响前面的（这里唯一的变换方式只有在两个监狱中变换【起码我一开始是这么想的】）

但后来想到其实不用进行变换，因为有一个很重要的性质叫 仇人的仇人就是朋友同时，只有两座监狱，蒟蒻灵光一闪！

这样问题一下子就变得很简单了，对于新加入的边，进行某些亦敌亦友的操作后一定就可以轻松解决上面那个问题了（这个问题会在下面详细说到）

如何实现

除了一般的并茶几数组，还有维护一个东西叫仇人数组的东西 这个仇人数组怎么处理呢？我们使用如下方法

对于还没有敌人，而被处理到的罪犯，我们更新仇人为另一个罪犯

对于已经有敌人的罪犯，直接把和他有冲突的罪犯和仇人合并

正确性好像很显然

想到这些，这道题目就已经解决了

代码

一点注意：对于完美情况要输出0

#include <bits/stdc++.h>

using namespace std;

const int maxn=100005;

struct edge{
    int u,v,w;
}e[maxn];
int fa[maxn<<1],dr[maxn<<1];
int n,m;

bool cmp(edge x,edge y){
    return x.w>y.w;
}

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

inline int find(int x){
    if(fa[x]==x)return x;
    fa[x]=find(fa[x]);
    return fa[x];
}

bool judge(int x,int y){
    if(find(x)==find(y))return 1;
    else return 0;
}

inline void merge(int x,int y){
    fa[find(x)]=find（y);
}

int main(){
    memset(dr,0,sizeof(dr));
    n=read();m=read();
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    for(int i=1;i<=m;i++){
        e[i].u=read(),e[i].v=read(),e[i].w=read();
    }
    int tag=0;
    sort(e+1,e+m+1,cmp）;
    for(int i=1;i<=m;i++){
        if(judge(e[i].u,e[i].v)){
            cout<<e[i].w;
            tag=1;
            break;
        }
        else{
            if(!dr[e[i].u]){
                dr[e[i].u]=e[i].v;
            }
            else{
                merge（dr[e[i].u],e[i].v);
            }
            if(!dr[e[i].v]){
                dr[e[i].v]=e[i].u;
            }
            else{
                merge（dr[e[i].v],e[i].u);
            }
        }
    }
    if(!tag)cout<<"0";
    return 0;
}

代码中使用了若干中文括号，直接复制将会ce；