bzoj 1433: [ZJOI2009]假期的宿舍 — 最大流

  • 2017-04-20
  • 0
  • 0

 

1433: [ZJOI2009]假期的宿舍

Time Limit: 10 Sec  Memory Limit: 162 MB

Description

Input

Output

Sample Input

1
3
1 1 0
0 1 0
0 1 1
1 0 0
1 0 0

Sample Output

ˆ ˆ

HINT

对于30% 的数据满足1 ≤ n ≤ 12。
对于100% 的数据满足1 ≤ n ≤ 50,1 ≤ T ≤ 20。

 

我们从源点向所有住宿的人连边,从所有的床位连向汇点,然后再从人连向他所认识的人的床位

这样建边,然后跑最大流

这样答案如果和住宿人数相等则满足,否则不满足

 

评论

还没有任何评论,你来说两句吧