ssl 2603 네트워크 흐름 24 문제 3 최소 경로 덮어 쓰기 문제

질문 설명:
그림 G = (V, E) 을 지정 합 니 다.설정 P 는 G 의 간단 한 길 (정점 이 교차 하지 않 음) 의 집합 이다.V 의 모든 정점 이 P 의 한 길에 있다 면 P 는 G 의 경로 로 덮어 쓴다 고 합 니 다.P 중로 경 은 V 의 어느 정점 에서 든 시작 할 수 있 고 길이 도 임 의적 이 며 특히 0 이 될 수 있다.G 의 최소 경 로 는 G 에 포 함 된 경로 의 개수 가 가장 적은 경로 로 덮어 씁 니 다.유효한 알고리즘 을 설계 하여 루프 없 는 그림 G 의 최소 경 로 를 덮어 씁 니 다.알림: 설정 V = {1, 2,..., n}, 구조 네트워크 G1 = (V1, E1) 은 다음 과 같 습 니 다.
각 변 의 용량 은 모두 1 이다.네트워크 G1 의 (0 x, 0 y) 최대 흐름 을 구 합 니 다.
« 프로 그래 밍 작업:
주어진 주어진 링 없 는 그림 G 에 대해 서 는 G 의 최소 경 로 를 찾 아 덮어 씁 니 다.
입 출력 형식
입력 형식: 첫 번 째 줄 에는 두 개의 정수 n 과 m 가 있 습 니 다.n 은 무 환 도 G 의 정점 을 정 하고 m 는 G 의 변 수 를 정 합 니 다.다음 m 줄 은 줄 마다 2 개의 정수 i 와 j 가 있 는데 하 나 는 방향 변 (i, j) 이 있 음 을 나타 낸다.
출력 형식: 첫 줄 부터 줄 마다 경 로 를 출력 합 니 다.파일 의 마지막 줄 은 최소 경로 입 니 다.
입 출력 샘플
입력 샘플 \ # 1: 11 12 1 2 1 3 1 4 5 3 4 7 5 8 9 7 10 9 11 출력 샘플 \ # 1: 1 4 7 10 11 2 5 8 3
주의: 그림 의 가장 작은 경 로 를 덮어 쓰 는 문 제 를 구하 고 덮어 쓰 는 경 로 를 출력 해 야 합 니 다.
분석: 새로운 그림 을 만 들 고 G 의 모든 점 i 를 새 그림 에서 두 개의 점 i, i '로 분해 합 니 다. 만약 에 G 에' i, j '가 존재 하면 새 그림 에서' i, j '> 를 연결 합 니 다. 분명히 새 그림 은 2 분 그림 입 니 다. 최대 일치 하 는 것 을 구하 면 (N - 새 그림 의 최대 일치 하 는 값) 은 가장 작은 경로 덮어 쓰기 값 입 니 다.출력 경 로 는 각 점 에서 시작 하여 옮 겨 다 닙 니 다. i 의 대 점 j '로 달 려 갈 수 있 기 때문에 다음 에는 j 부터 검색 해 야 합 니 다. 만약 에 한 쪽 의 권리 가 0 이면 흐 르 는 것 이 있 습 니 다. 바로 해 입 니 다.
코드:

const
 maxn=2003;
 maxm=200003;
type
 node=record
  y,c,next,op:longint;
 end;

var
 e,n,m,s,t,ans,d,x,y,i,j,num:longint;
 ls,dis,q,cur,path,v:array [0..maxn] of longint;
 g:array [0..maxm*2] of node;
procedure add(u,v,c:longint);
begin
 inc(e);
 g[e].y:=v; g[e].c:=c; g[e].op:=e+1; g[e].next:=ls[u]; ls[u]:=e;
 inc(e);
 g[e].y:=u; g[e].c:=0; g[e].op:=e-1; g[e].next:=ls[v]; ls[v]:=e;
end;

function bfs:boolean;
 var i,head,tail,tt,u:longint;
begin
 for i:=s to t do
  dis[i]:=0;
 dis[s]:=1;
 head:=0; tail:=1;
 inc(tail);
 q[tail]:=s;
 while head<=tail do
  begin
   inc(head);
   u:=q[head];
   i:=ls[u];
   while i>0 do
    begin
     if (g[i].c<>0) and (dis[g[i].y]=0) then
      begin
       dis[g[i].y]:=dis[u]+1;
       if g[i].y=t then exit(true);
       inc(tail);
       q[tail]:=g[i].y;
      end;
     i:=g[i].next;
    end;
  end;
 exit(false);
end;

function min(x,y:longint):longint;
 begin
  if xthen exit(x)
         else exit(y);
 end;

function dfs(x,maxf:longint):longint;
var ret,i,f:longint;
 begin
  if (x=t) or (maxf=0) then exit(maxf);
  ret:=0;
  i:=cur[x];
  while i>0 do
   begin
    if (g[i].c<>0) and (dis[g[i].y]=dis[x]+1) then
     begin
      f:=dfs(g[i].y,min(g[i].c,maxf));
      dec(g[i].c,f);
      inc(g[g[i].op].c,f);
      ret:=ret+f;
      if ret=maxf then break;
     end;
    i:=g[i].next;
   end;
  exit(ret);
 end;

procedure dinic;
 var i:longint;
begin
 while bfs do
  begin
   for i:=s to t do
    cur[i]:=ls[i];
   ans:=ans+dfs(s,maxlongint);
  end;
end;

procedure find(x:longint);
 var i,y:longint;
begin
 if (x>2*n) or (x<0) then exit;
 v[x]:=1;
 inc(num);
 path[num]:=x;
 i:=ls[x];
 while i>0 do
  begin
   y:=g[i].y;
   if (v[y]=0) and (y>0) and (g[i].c=0) then
    find(y-n);
   i:=g[i].next;
  end;
end;

begin
 readln(n,m);
 for i:=1 to m do
  begin
   readln(x,y);
   add(x,y+n,1);
  end;
 for i:=1 to n do
  add(0,i,1);
 for i:=n+1 to 2*n do
  add(i,2*n+1,1);
 s:=0; t:=2*n+1;
 fillchar(v,sizeof(v),0);
 dinic;
 for i:=1 to n do
  begin
   num:=0;
   if v[i]=1 then continue;
   fillchar(path,sizeof(path),0);
   find(i);
   for j:=1 to num do
    write(path[j],' ');
   writeln;
  end;
 writeln(n-ans);
end.