关押罪犯

发表于
字数统计: 875
题目描述

$S$城现有两座监狱，一共关押着$N$名罪犯，编号分别为$1$~$N$。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为$c$的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为$c$的冲突事件。

每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到$S$城$Z$市长那里。公务繁忙的$Z$市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。

在详细考察了$N$名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。

那么，应如何分配罪犯，才能使$Z$市长看到的那个冲突事件的影响力最小？这个最小值是多少？

$N \le 20000$,$M \le 100000$,$0 < c_j \le 1000000000$

方案一:并查集 + 贪心
贪心方案很显然,从$c$大的罪犯对开始合并,直到不能合并了就输出
具体实现过程是定义一个$en$数组储存敌人所在并查集的根节点
每次对于有仇恨的$i$和$j$,进行$unionn$操作,合并$j$和$en[i]$即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//每次写这种整整齐齐的代码就感觉非常愉悦是我的错觉吗

struct badguy{
    int tom ,jerry ,cheese;
    bool operator < (badguy host){
        return cheese > host.cheese;
    }
}rela[100010];

int main(){
    ...
    sort(rela + 1 , rela + m + 1);
    for(int i = 1 ; i <= m ; ++ i){
        int TOM = rela[i].tom , JERRY = rela[i].jerry ;
        if(check(TOM , JERRY)){
            printf("%d",rela[i].cheese);
            return 0 ;
        }
        if(! en[TOM]) en[TOM] = JERRY ;
        else unionn(en[TOM] , JERRY);
        if(! en[JERRY]) en[JERRY] = TOM ;
        else unionn(en[JERRY] , TOM);
    }
    printf("%d",0);//记得特判不会有影响的情况
    return 0 ;
}

方案二:二分图判定 + 二分
判定:是否存在一种分配罪犯的方案,使$Z$市长看到的那个冲突事件的影响力不超过$standard$
即在$c$超过$standard$的罪犯对之间连边
如果能形成二分图,那么返回$true$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
bool dfs(int node, int col){
    color[node] = col;
    for(int i = head[node]; i; i = ne[i]){
        if(!color[To = to[i]]){
            if(!dfs(To, 3-col)) return false;
        }else if(color[To] == col) return false;
	}
    return true;
}

bool check(LL stand){
    int from = find(stand);//二分找到c值大于等于stand的罪犯对下标
    clear();//清空数组
    add();//连边
    for(int i = 1; i <= n; ++ i){
        if(!color[i] && !dfs(i, 1)) return false;
    }
    return true;
}

int main(){
    ...
    sort(re + 1, re + m + 1);
    LL l = 0, r = re[m].cheese;
    while(l < r){
        LL mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%lld", max((LL)0, r-1));
    //r是最小的能够形成二分图的standard,那么r-1就是最大的不能形成二分图的standard
    return 0;
}