#P18762. [2025NA]Buying Jerseys
[2025NA]Buying Jerseys
题目描述
一项足球联赛中共有 名球员。球员之间有 对互相不愿同队的关系,称为对手关系。每名球员可以采取以下三种安排之一:
- 加入穿球衣的球队,费用为 ;
- 加入不穿球衣的球队,费用为 ;
- 退出联赛,退费成本为 。
对任意一对存在对手关系的球员,如果他们都没有退出,则不能被安排进同一支球队。
题目保证上一赛季存在一种将全部球员分配到两队、且不违反对手关系的方案。这一方案会以二进制字符串给出,其中 1 表示穿球衣的球队,0 表示不穿球衣的球队。
本赛季允许重新分队,也可以让部分球员退出。求所有安排中,联赛承担的最小总费用。
输入格式
第一行包含两个整数 ,满足:
接下来 行,每行两个整数 (),表示球员 与 是对手。每对关系仅出现一次。
最后一行是长度为 的二进制字符串 。若 ,表示球员 上赛季在穿球衣队,否则在不穿球衣队。保证 对所有对手关系均合法。
输出格式
输出一个整数,即最小总费用。
样例 1
输入
4 1
1 2
0101
输出
1
样例 2
输入
4 4
1 2
3 4
1 4
2 3
0101
输出
2
样例 3
输入
8 7
1 2
1 3
1 4
1 5
2 6
2 7
2 8
01111000
输出
3