| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
我的算法刚开始当成了二分图匹配,对于每头牛,直接把它喜欢吃的与喜欢喝的连边。。。十分钟打完提交 WA 。。。想了几分钟,发现是一头牛最多只能吃一份吃的与一份喝的。。。而那样做会算得多。。。
然后我就傻了。。。脑残地想了很多种拆点的匹配方法。。。过了20分钟忽然发现,我只需要在最开始的二分图匹配的方法上面改改,把每头牛拆成两个点,之间的容量为 1即可。。。
然后十分钟打完网络流,提交 AC 了。。。。
下面是我的构图,正确的构图 :
procedure solve ;
var i , j , n , f , d , u , v , f0 , d0
: longint ;
begin
fillchar (vr , sizeof (vr) , $ff) ; tot := -1 ;
readln (n , f , d) ;
s := n + n + f + d + 1 ; t := s + 1 ; z := t ;
for i := 1 to f do
addarc (s , i , 1) ;
for i := 1 to d do
addarc (f + n + n + i , t , 1) ;
for i := 1 to n do
addarc (f + i , f + n + i , 1) ;
for i := 1 to n do begin
read (f0 , d0) ;
for j := 1 to f0 do begin
read (u) ;
addarc (u , f + i , 1) ;
end ;
for j := 1 to d0 do begin
read (u) ;
addarc (f + n + i , f + n + n + u , 1) ;
end ;
end ;
sap ;
writeln (flow) ;
end ;
下面的这个是刚开始的错误的构图 - -b
procedure solve ;
var i , j , k , p , ans , n0 , m0
: longint ;
begin
readln (p , n , m) ;
for p := 1 to p do begin
read (n0 , m0) ;
for i := 1 to n0 do
read (a[i]) ;
for i := 1 to m0 do
read (b[i]) ;
for i := 1 to n0 do
for j := 1 to m0 do
g[a[i]][b[j]] := true ;
end ;
now := 1 ; ans := 0 ;
for i := 1 to n do begin
inc (now) ;
if (find (i)) then
inc (ans) ;
end ;
writeln (ans) ;
end ;
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator