# 二分图

Acwing379 捉迷藏

原题链接:Acwing379

题目描述:Vani 和 cl2 在一片树林里捉迷藏。

这片树林里有 N 座房子,M 条有向道路,组成了一张有向无环图。

树林里的树非常茂密,足以遮挡视线,但是沿着道路望去,却是视野开阔。

如果从房子 A 沿着路走下去能够到达 B,那么在 A 和 B 里的人是能够相互望见的。

现在 cl2 要在这 N 座房子里选择 K 座作为藏身点,同时 Vani 也专挑 cl2 作为藏身点的房子进去寻找,为了避免被 Vani 看见,cl2 要求这 K 个藏身点的任意两个之间都没有路径相连。

为了让 Vani 更难找到自己,cl2 想知道最多能选出多少个藏身点。

……

READ MORE

Acwing378 骑士放置

原题链接:Acwing378

题目描述:给定一个 N * M 的棋盘,有一些格子禁止放棋子。

问棋盘上最多能放多少个不能互相攻击的骑士(国际象棋的“骑士”,类似于中国象棋的“马”,按照“日”字攻击,但没有中国象棋“别马腿”的规则)。

……

READ MORE

Acwing376 机器任务

原题链接:Acwing376

题目描述:有两台机器 A,B 以及 K 个任务。

机器 A 有 N 种不同的模式(模式 0 ~ N - 1),机器 B 有 M 种不同的模式(模式 0 ~ M - 1)。

两台机器最开始都处于模式0。

每个任务既可以在 A 上执行,也可以在 B 上执行。

对于每个任务 i,给定两个整数 a[i] 和 b[i],表示如果该任务在 A 上执行,需要设置模式为 a[i],如果在 B 上执行,需要模式为 b[i]。

任务可以以任意顺序被执行,但每台机器转换一次模式就要重启一次。

求怎样分配任务并合理安排顺序,能使机器重启次数最少。

……

READ MORE

Acwing257 关押罪犯

原题链接:Acwing257

题目描述:S 城现有两座监狱,一共关押着 N 名罪犯,编号分别为1~N。

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

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

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

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

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

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

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

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

假设只要处于同一监狱内的某两个罪犯间有仇恨,那么他们一定会在每年的某个时候发生摩擦。那么,应如何分配罪犯,才能使 Z 市长看到的那个冲突事件的影响力最小?这个最小值是多少?

……

READ MORE

Recents
Categories
Tags
Links