Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom7月前

12/7
16:08
最小割

[bzoj 1585] [Usaco2009 Mar]Earthquake Damage 2 地震伤害

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

Farmer John的农场里有P个牧场,有C条无向道路连接着他们,第i条道路连接着两个牧场Ai和Bi,注意可能有很多条道路连接着相同的Ai和Bi,并且Ai有可能和Bi相等。Farmer John在1号牧场里。由于地震,某些牧场被损坏,但由于信春哥,C条道路没有一条损坏。有N头奶牛,他们在不同的牧场里,于是N <= P。他们一一向Farmer John报告。第i头奶牛报告给Farmer John一个整数Report_i,代表第Report_i个牧场没有损毁,但不能够从第Report_i个牧场经过一些没有损坏的牧场到达1号牧场。现在Farmer John想知道,最少有多少损坏的牧场。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行三个整数 P,C,N

第2..C+1行:每行两个整数Ai,Bi

第C+2..C+N+1行:第C+1+i行包含一个整数,Report_i

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

一个整数,代表最少有多少损坏的牧场

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

5 5 2
1 2
2 3
3 5
2 4
4 5
4
5

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

1
【数据规模】
1 <= P <=3000
1 <= C <=20000

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

拆点最小割。

S->1 c=INF

提到的点x x'->T c=INF

对于每个点x,为1或是提到的点 x->x' c=INF

对于每个点x,不为1且不是提到的点 x->x' c=1

对于原图每条边x->y x'->y c=INF y'->x c=INF

 

[bzoj 1585] [Usaco2009 Mar]Earthquake Damage 2 地震伤害