这题感觉其他的题解写的都不是很清楚(也可能是因为我太弱),导致我并没有看懂。我于是请教了 THU 学长 Mr_Wu,然后他用了 秒就切了这道题,并且教会了我。
本蒟蒻最近在复习图论,听机房里的大佬说这道题是一道差分约束裸题,就跑过来做了这道题。
简单介绍一下差分约束系统:差分约束系统就是给出n个变量 ,在m个形如 的不等式的约束下,求解所有满足这些不等式的解。
把机器A的n个模式作为n个左部节点,机器B的m个模式作为m个右部节点,每个任务是一条边,连接a[i]和b[i]。由于每个任务需要在A和B之间选一个,所以求这个二分图的最小点覆盖就相当于用最少的模式完成任务。