Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我的算法

Posted by IceKingdom at 2009-07-05 11:13:04 on Problem 3281 and last updated at 2009-07-05 11:17:12
刚开始当成了二分图匹配,对于每头牛,直接把它喜欢吃的与喜欢喝的连边。。。十分钟打完提交 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator