# 匈牙利算法

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

Recents
Categories
Tags
Links