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