您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

《算法竞赛进阶指南》0x49 T1 关押罪犯

题目传送门

题目描述

S 城现有两座监狱,一共关押着 N 名罪犯,编号分别为 1∼N。

他们之间的关系自然也极不和谐。

很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突。

我们用“怨气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,则这两名罪犯之间的积怨越多。

如果两名怨气值为 c 的罪犯被关押在同一监狱,他们俩之间会发生摩擦,并造成影响力为 c 的冲突事件。

每年年末,警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表,然后上报到 S 城 Z 市长那里。

公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力,如果影响很坏,他就会考虑撤换警察局长。

在详细考察了 N 名罪犯间的矛盾关系后,警察局长觉得压力巨大。

他准备将罪犯们在两座监狱内重新分配,以求产生的冲突事件影响力都较小,从而保住自己的乌纱帽。

假设只要处于同一监狱内的某两个罪犯间有仇恨,那么他们一定会在每年的某个时候发生摩擦。

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

题解

由于市长只会看到冲突事件影响力最大的一件事,所以我们可以采用贪心策略,先将怨气值从大到小排序
想要使最后的最大怨气值最小,最好就是尽量让怨气值大的两名罪犯分在两个监狱里。所以每次加入一对罪犯,就需要判断其在不在一个并查集里,若不在,那么将两名罪犯加入到补集之中。然后若在一个并查集里,那么我们可以直接输出,因为最大权值,已经被贪心锁定好了.

code
#include <bits/stdc++.h>
using namespace std;
const int N=100100;
int n,m,fa[N];
struct node
{
    int a,b;
	long long c;
}e[N];
bool cmp(node a,node b)
{
    return a.c>b.c;
}
int find(int x)
{
	if(x==fa[x]) return x;
	else return fa[x]=find(fa[x]);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>e[i].a>>e[i].b>>e[i].c;
    for(int i=1;i<=n*2;i++) fa[i]=i;
    sort(e+1,e+1+m,cmp);
    for(int i=1;i<=m;i++)
    {
        int x=find(e[i].a);
        int y=find(e[i].b);
        if(x==y)
        {
            cout<<e[i].c;
            return 0;
        }
        fa[y]=find(e[i].a+n);
        fa[x]=find(e[i].b+n);
    }
    cout<<0;
    return 0;
}

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进