特殊的最小路径覆盖

回顾一下经典的最小路径覆盖问题是每个点都恰好被一条路径覆盖

我们把有向无环图的点拆成i,i',对于原图中边i--->j，连边i-->j'

做最大匹配，答案是原图点数-最大匹配

但这道题每个点可以被覆盖多次，所以我们考虑先dfs出每个点可以访问的点

然后拆点，如果i可以到达j，那么连边i-->j'，答案是原图点数-最大匹配

为什么呢，感性的想一下，在最小路径覆盖的基础上既然每个点可以被多次经过

那么干脆我们把两个可达的点认为是直接飞过去就好了~ ~

1 type node=record 2        point,next:longint; 3      end; 4  5 var edge:array[0..200010] of node; 6     a:array[0..510,0..510] of boolean; 7     p,cx,cy:array[0..510] of longint; 8     v:array[0..510] of boolean; 9     x,y,n,m,i,j,ans,len:longint;10 11 procedure add(x,y:longint);12   begin13     inc(len);14     edge[len].point:=y;15     edge[len].next:=p[x];16     p[x]:=len;17   end;18 19 function find(x:longint):longint;20   var i,y:longint;21   begin22     i:=p[x];23     while i<>-1 do24     begin25       y:=edge[i].point;26       if not v[y] then27       begin28         v[y]:=true;29         if (cy[y]=-1) or (find(cy[y])=1) then30         begin31           cx[x]:=y;32           cy[y]:=x;33           exit(1);34         end;35       end;36       i:=edge[i].next;37     end;38     exit(0);39   end;40 41 procedure dfs(x:longint);42   var i,y:longint;43   begin44     i:=p[x];45     v[x]:=true;46     while i<>-1 do47     begin48       y:=edge[i].point;49       if not v[y] then dfs(y);50       i:=edge[i].next;51     end;52   end;53 54 begin55   readln(n,m);56   while (n<>0) do57   begin58     ans:=0;59     len:=0;60     fillchar(p,sizeof(p),255);61     fillchar(a,sizeof(a),false);62     for i:=1 to m do63     begin64       readln(x,y);65       add(x,y);66       a[x,y]:=true;67     end;68     for i:=1 to n do69     begin70       fillchar(v,sizeof(v),false);71       dfs(i);72       for j:=1 to n do73         if v[j] and (i<>j) and not a[i,j] then74           add(i,j);75     end;76     fillchar(cx,sizeof(cx),255);77     fillchar(cy,sizeof(cy),255);78     for i:=1 to n do79       if cx[i]=-1 then80       begin81         fillchar(v,sizeof(v),false);82         ans:=ans+find(i);83       end;84     writeln(n-ans);85     readln(n,m);86   end;87 end.