Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem E: 毕业季

Problem E: 毕业季

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 20  Solved: 7
[Submit][Status][Web Board]

Description

又到了毕业季了,同学们有感受到伤感的气息吗(┬_┬)。
大三的同学们也开始焦虑起来了,除了少部分准备出国的同学,大部分人计划读研或工作。大家都有不同的打算,但是大家都不想和现在的同学、恋人分开→_→。
现在某班有N人,要统计未来意向,每个人都想避免自己和同学恋人有不同的打算,以免天各一方。有时候他们会为了对方改变自己的决定。现在给出每个人的初始打算(读研或工作)且给出朋友及恋人关系。假设最后改变自己最初打算的人数为x,持有不同打算的朋友或者恋人的对数为y,你能找到某种每个人的最终打算方案,使得x+y最小吗?

Input

有多组样例,读入到文件结束。
第一行输入3个整数N, M表示共有N人(2 <= N <= 300),有M对朋友或恋人关系关系(0<=M<=N*(N-1)/2)。
接下来是N个数,表示每个人的初始打算,0表示读研,1表示工作。
接下来是M行,每行3个数a, b, c。(c = 0, 1)
c = 1表示a和b是恋人关系。
c = 0表示a和b是朋友关系。
(1<=a,b<=N, 无重边,且a和b不可能既是恋人也是朋友,且a != b)。

Output

对每组样例,请先输出“Case #x:”,x表示第几组数据。
然后换一行输出x+y。

Sample Input

3 3
1 0 0
1 2 1 
1 3 0
3 2 1
6 6
1 1 1 0 0 0
1 2 1 
2 3 1
4 2 1
3 5 0
4 5 0
5 6 0

Sample Output

Case #1:
1
Case #2:
2

HINT

[Submit][Status][Web Board]